RS
RS
Joined: Feb 11, 2014
  • Threads: 62
  • Posts: 8623
January 25th, 2017 at 5:55:15 AM permalink
You have the numbers 1 through 100 inclusive and some random amount of numbers have been removed (between 1 number and 99 numbers have been removed). How do you determine which numbers were removed?

You know the starting list had numbers 1-100 inclusive.
You are not told how many have been removed.
You are given a variable for each number remaining.
You can not count how many variables you've been given.
You can not directly look at the value of any variable.
You can apply one or more mathematical formulas to the variables given.
You can use a program to determine which numbers are missing.

You CANNOT do something like
For x = 0 to size.array {
For y = 0 to 99 {
If array[x] == y {
Print y;
}}}
DRich
DRich
Joined: Jul 6, 2012
  • Threads: 78
  • Posts: 7994
January 25th, 2017 at 7:39:27 AM permalink
cumm=0
for x = 0 to size.array
cumm ||= (1 shl (array[x]-1))

for x= 1 to 100
if !(cumm && (1 shl (x-1))) print x


Something like this will print in order the numbers that were not in the original list.
Order from chaos
Romes
Romes
Joined: Jul 22, 2014
  • Threads: 28
  • Posts: 5518
January 25th, 2017 at 7:42:21 AM permalink
//theList[100] was initialized above to have every number, 1-100 in it, with 0 being a placeholder for 'X'.
//finalList[100] was initialized above to have an 'X' placeholder in every slot.

for (int x = 0; x<100; x++)
{
finalList[theList[ i ]] = theList[ i ];
}

/*
finalList contains an array where all the remaining numbers are in their respective slot and all of the removed numbers still have 'X' in the slot.
simply print out finalList where finalList[ i ] != 'X'
*/

gg

..Yeah yeah I get you don't want programming, but you're asking a question with so many restrictions that clearly one must solve it exactly how you want it solved, instead of just solving the problem =). I'm a rebel... Don't play those games 8-).
Playing it correctly means you've already won.
RS
RS
Joined: Feb 11, 2014
  • Threads: 62
  • Posts: 8623
January 25th, 2017 at 9:38:05 AM permalink
Neither of those are mathematical answers. :(
ThatDonGuy
ThatDonGuy 
Joined: Jun 22, 2011
  • Threads: 106
  • Posts: 4959
January 25th, 2017 at 9:42:17 AM permalink
Well, the "obvious" answer (to me, anyway) is, raise 2 to the power of each integer, and add them up. Express the sum as a binary number; going from right to left, N is one of the numbers if and only if the (N+1)th digit from the right (i.e. the rightmost digit is "first from the right") is 1.

However, that smacks of counting the numbers.
rsactuary
rsactuary
Joined: Sep 6, 2014
  • Threads: 22
  • Posts: 1865
January 25th, 2017 at 9:45:44 AM permalink
Quote: ThatDonGuy

Well, the "obvious" answer (to me, anyway) is, raise 2 to the power of each integer, and add them up. Express the sum as a binary number; going from right to left, N is one of the numbers if and only if the (N+1)th digit from the right (i.e. the rightmost digit is "first from the right") is 1.

However, that smacks of counting the numbers.



Clever though!
MathExtremist
MathExtremist
Joined: Aug 31, 2010
  • Threads: 88
  • Posts: 6526
January 25th, 2017 at 4:34:38 PM permalink
Quote: RS

You have the numbers 1 through 100 inclusive and some random amount of numbers have been removed (between 1 number and 99 numbers have been removed). How do you determine which numbers were removed?

You know the starting list had numbers 1-100 inclusive.
You are not told how many have been removed.
You are given a variable for each number remaining.
You can not count how many variables you've been given.
You can not directly look at the value of any variable.
You can apply one or more mathematical formulas to the variables given.

You can use a program to determine which numbers are missing.

I don't think this is exactly what you meant, because there are no programming languages I know about where applying mathematical formulas to a variable doesn't evaluate (look at) the value of that variable first. Otherwise how could you apply a formula to it?

What I think you meant is something like what ThatDonGuy proposed. Basically, I'd turn your list into a 100-bit binary number. Then what I'd do is take the ones'-complement of that number and then turn it back into a list, which would then be the list of numbers that were removed. Exactly how I'd do that depends on exactly the data structures you're giving me to start with.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563
RS
RS
Joined: Feb 11, 2014
  • Threads: 62
  • Posts: 8623
January 25th, 2017 at 5:03:29 PM permalink
Quote: MathExtremist

I don't think this is exactly what you meant, because there are no programming languages I know about where applying mathematical formulas to a variable doesn't evaluate (look at) the value of that variable first. Otherwise how could you apply a formula to it?

What I think you meant is something like what ThatDonGuy proposed. Basically, I'd turn your list into a 100-bit binary number. Then what I'd do is take the ones'-complement of that number and then turn it back into a list, which would then be the list of numbers that were removed. Exactly how I'd do that depends on exactly the data structures you're giving me to start with.



Perhaps a better way to describe it is to say you must apply a formula or something to every number in the list (i.e.: total sum) and you can only use that final number to determine which in the list are missing.

How would you do it if you couldn't use ThatDonGuy's method?
MathExtremist
MathExtremist
Joined: Aug 31, 2010
  • Threads: 88
  • Posts: 6526
January 25th, 2017 at 8:30:09 PM permalink
Quote: RS

Perhaps a better way to describe it is to say you must apply a formula or something to every number in the list (i.e.: total sum) and you can only use that final number to determine which in the list are missing.

How would you do it if you couldn't use ThatDonGuy's method?

You could use powers of 100 instead of powers of 2 and just make it human-readable instead. The formula is SUM (for each N in the list) N * 100^(N-1).

If all the numbers were in the set, that would yield a 201-digit number that starts with 100999897969594... and ends with ...0504030201. However, if a number is missing, there will be two zeros in the space where it should be. E.g., if 4 and 2 were missing, the last few digits would look like 0500030001. So you can either eyeball it and figure out the gaps in your head, or you can subtract that result number from the "full set" number and get the missing numbers in the same format. E.g., ...0504030201 - ...0500030001 = ...0004000200. So now I know 04 and 02 are missing.
"In my own case, when it seemed to me after a long illness that death was close at hand, I found no little solace in playing constantly at dice." -- Girolamo Cardano, 1563

  • Jump to: