List of 100

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;
}}}

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.

//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-).

Neither of those are mathematical answers. :(

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.

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!

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.

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?

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.