Author |
Topic: Missing Integer In Array (Read 4971 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Missing Integer In Array
« on: Oct 14th, 2002, 8:11pm » |
 Quote  Modify
|
Here's a simple question Microsoft asked a friend of mine at a recent interview. You have a 99 cell array. In each cell you put an integer belonging to the set {1,2,...,100}. No two cells contain the same integer. Thus when the array filling is complete, one of the integers from 1 to 100 is not present in the array. Determine which integer is missing from the array.
My solution (highlight area below to see):
// The most intuitive thing to do is make a list of integers from 1 to 100, then look at the contents of each cell, and put a checkmark next to each integer on our list that has been seen. Finally, the integer without a checkmark next to it is the one that's missing. Making such a checkmark list could require the creation of a new array.
// A solution that requires less space could exploit a fact about arithmetic sums: the sum of all integers from 1 to n is n(n+1)/2, as Gauss demonstrated when he was a little tyke in elementary school. So we can start with this sum, and repeatedly subtract from it the contents of each cell in the array. After all the subtractions, the leftover value is the missing integer.
int x = 100(101)/2;
for (i = 1; i<=99; i++)
x = x - array[i];
print("Missing element: %d", x);
// Similarly, one could add up the contents of every cell, and then calculate how much that sum differs from 100(101)/2; the difference is the missing integer.
Is there a better solution?
|
| « Last Edit: Oct 14th, 2002, 8:16pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Missing Integer In Array
« Reply #1 on: Oct 15th, 2002, 1:20am » |
Quote Modify
|
on Oct 14th, 2002, 8:11pm, william wu wrote:
Is there a better solution?
|
|
Sort of. Your solution requires only linear time and constant space. You can't do better than linear time because you must examine every element in the array. Obviously you can't do better than constant space. The constant factors in your solution are also minimal.
However, your solution is subject to overflow when n grows beyond the square root of the maximum value that fits in a word. Here's a way around that, hidden by color.
Use XOR instead of addition: Precompute the XOR of all integers from 1 to n; set x to this value. Then make one pass through the array, XORing each cell into x. At the end, x will be the missing value.
Perhaps one can speed that up a factor of 2 by finding a fast way to compute the initial value of x. I don't know one offhand, but it seems like there should be one. I'm almost embarrassed to post before working that out, but I need to knock off and go to bed now.
|
| « Last Edit: Oct 15th, 2002, 1:21am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: Missing Integer In Array
« Reply #2 on: Oct 15th, 2002, 3:40pm » |
Quote Modify
|
Interesting question... how to compute the exclusive-or of the numbers 0 to n. Call it XOR(n).
Let N = floor(log2(n)). I just mean that N is the number of bits in n, minus 1.
XOR(0) = 0
XOR(1) = 1
XOR(n) = 2N + XOR(n-2N) when n is even and >1
XOR(n) = XOR(n-2N) when n is odd and >1
I think one can see why this works most easily by inspection... it is probably a little messy to prove it.
So you can do it log(n) time.
I like the XOR answer a lot.
|
| « Last Edit: Oct 15th, 2002, 3:42pm by S. Owen » |
IP Logged |
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: Missing Integer In Array
« Reply #3 on: Oct 15th, 2002, 7:11pm » |
Quote Modify
|
It's actually not that messy... I've managed to sort out the details. It turns out to be a little variation on Gauss's proof.
Let N and XOR(n) be as you defined it, and let n be our number. Hence n has N+1 binary places. Consider the XOR of the first 2N numbers, 0 through 2N-1: the (N+1)-th place of that will be 0, naturally, and, surprisingly, all the others will be, too, if N > 1. Here is where the little variation comes in: given x between 0 and 2N-1, there will be x' lying in that same interval such that x XOR x' = 2N-1 = 1...1 (N ones). This x' is obtained uniquely from x by reversing all but the most significant (which will remain 0) of x's binary places. Therefore, XOR(2N-1) is equal to the XOR of 2N-1 strings of N ones. If N > 1, this will be a string of N zeroes.
The rest falls out. For given n and N, n-2N+1 numbers between 0 and n will have 1 as their most significant digit; if n is odd, n-2N+1 is even, and the most significant 1's will cancel; otherwise they won't. So we have your formula:
XOR(n) = 2N + XOR(n-2N) for n even
XOR(n) = XOR(n-2N) for n odd.
However, because of the N>1 restriction above, I must add two other base cases:
XOR(00) = 00
XOR(01) = 01
XOR(10) = 11
XOR(11) = 00
But it gets better!  If n is even or odd, n-2N will still be even or odd, respectively. So, by fiddling around, you can see that:
XOR(n) = n if n ends in 00
XOR(n) = 1 if n ends in 01
XOR(n) = n+1 if n ends in 10
XOR(n) = 0 if n ends in 11.
The third case amounts to changing the 2 last bits of n to 11, so you might even say that the XOR function can be calculated in constant time. Well, that was unexpected!
|
| « Last Edit: Oct 15th, 2002, 7:15pm by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: Missing Integer In Array
« Reply #4 on: Oct 15th, 2002, 8:51pm » |
Quote Modify
|
Very nice result!
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Missing Integer In Array
« Reply #5 on: Oct 15th, 2002, 10:36pm » |
Quote Modify
|
Good job picking up the ball and running with it. You can get the final result more simply just by writing down the numbers from 0 to 7 or 0 to 15 in binary and observing the pattern in each column. For the low order bit, the initial 01010101... pattern changes to 011000110... For all other bits, the pattern 0000...001111...11 (i.e., an even number of 0's followed by an even number of 1's) changes to 0000...001010...10. So for even n, bits other than the low-order bit remain unchanged; for odd n, they change to zero. For all n, the low-order bit changes to the xor of the two low-order bits. This is the same result Pietro stated.
|
| « Last Edit: Oct 16th, 2002, 9:29am by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: Missing Integer In Array
« Reply #6 on: Oct 16th, 2002, 11:06am » |
Quote Modify
|
I'm a bit late, but here's a closed-form C expression for calculation XOR:
Code:
inline unsigned XorSum(unsigned x)
{
return x&1 ^ ((x&2)>>1) | (((x&1)^1) * (x&~1));
}
|
|
|
|
IP Logged |
My arcade cabinet
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Missing Integer In Array
« Reply #7 on: Oct 22nd, 2002, 1:58am » |
Quote Modify
|
Wow! These are some seriously cool tricks. I will add them to my mental toolbox with great pleasure. Heh I felt like jumping up and down when I read this thread, but I was in a lab and it would've been a weird scene. Anyways you guys are great teachers. I didn't even know you could use XORs like that until I considered the following relations:
// (for the unacquainted):
// If a and b are bits, a XOR b is 1 if a != b, 0 otherwise
A XOR B = C
A XOR B XOR B = C XOR B // B == B, so B XOR B is 0 since there are no bitwise differences
A XOR 0 = C XOR B
A = C XOR B
The constant-time XOR is very cool too. Man, there was a lot more to this riddle than I expected.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Shiva Krovi
Guest
|
|
Re: Missing Integer In Array
« Reply #8 on: Apr 17th, 2003, 9:54pm » |
Quote Modify
 Remove
|
I think I have a simpler solution. Since the array is 1.....100 and finding a missing number since all are unique between 1 and 100.
missinNumber = 5050 - Sum[1........100];
I hope you get the idea. The sum of 1+2+3....100 = 5050. so the difference would give us the missing number for that array.
cheers,
-shiva
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: Missing Integer In Array
« Reply #9 on: Apr 18th, 2003, 5:51am » |
Quote Modify
|
Yeah, that's the usual answer -- it's in the first post of this thread. The advantage of the XOR version is that it's not vulnerable to overflow.
|
|
IP Logged |
|
|
|
Manuella
Guest
|
|
Re: Missing Integer In Array
« Reply #10 on: May 21st, 2003, 8:09am » |
Quote Modify
Remove
|
I think that it is possible to do this without looking at each element...any thoughts?
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: Missing Integer In Array
« Reply #11 on: May 21st, 2003, 8:34am » |
Quote Modify
|
Hmm... I'm not sure I see how that's possible.
Even if I looked at 98 values, and thus ruled out 98 of the 100 possible missing values, there would be no way to know which of the remaining 2 values was the missing one -- without looking at the last value. How could you know?
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Missing Integer In Array
« Reply #12 on: Nov 2nd, 2007, 11:45am » |
Quote Modify
|
@Jonathan_the_Red
Can you please explain how XOR in a single line is working here ?
|
|
IP Logged |
|
|
|
gotit
Uberpuzzler
Gender:
Posts: 804
|
|
Re: Missing Integer In Array
« Reply #13 on: Nov 2nd, 2007, 12:16pm » |
Quote Modify
|
There are 4 possibilities:
n ends with 00-->XOR(1,2,...n)=n;
n ends with 01-->XOR(1,2,...n)=1;
n ends with 10-->XOR(1,2,...n)=n+1;
n ends with 11-->XOR(1,2,...n)=0;
The key to undrstand the expression is to realize that the the term to the right of | reduces to 0 if n is odd and it reduces to n if n is even.Now if n is odd the expression reduces to 0^1(if n ends with 01) or 1^1(if n ends with 11).So we get either 1 or 0 as the result.
To consider the case for n is even, you must realize that XOR(1,2,..,n)=XOR(n,XOR(1,2,....,n-1)).If n ends with 00, n-1 ends with 11. So XOR(1,2,...n) in this case is XOR(n,0)=n. If n ends with 10,n-1 ends with 01 and XOR(1,2,..,n)=XOR(n,1)=n+1.
I hope I am clear.
|
|
IP Logged |
All signatures are false.
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Missing Integer In Array
« Reply #14 on: Nov 2nd, 2007, 12:59pm » |
Quote Modify
|
yups, now it is clear...
thank u... 
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print