7

Possible Duplicate:
Quickest way to find missing number in an array of numbers

Input: unsorted array A[1,..,n] which contains all but one of the integers in the range 0,..,n

The problem is to determine the missing integer in O(n) time. Each element of A is represented in binary, and the only operation available is the function bit(i, j), which returns the value of the jth bit of A[i] and takes constant time.

Any ideas? I think some sort of divide-and-conquer algorithm would be proper, but I can't think of what exactly I should do. Thanks in advance!

Community
  • 1
  • 1
hellohelloworld
  • 73
  • 3
  • If bit(i,j) is the ONLY operation available, how do you propose to implement a divide-and-conquer algorithm ? – High Performance Mark Oct 28 '10 at 07:59
  • @A. Rex: the possible dupe you linked doesn't have the same restriction on instructions, so I don't think it's necessarily a dupe. – Dan Puzey Oct 28 '10 at 22:23
  • This isn't a duplicate. In this problem, you only get to read O(n) of the n log n bits of the input A. If that's the only constraint (i.e. if operations besides bit(i, j)) are free, then you can still solve it, with a divide-and-conquer algorithm, sort of: the comment-sized description of the algorithm is to count the number of even and odd numbers, check which count doesn't match the one you'd get from 0...n, and recurse on that half of the input after throwing away the lowest bit. – Reid Barton Oct 30 '10 at 14:46
  • This isn't a duplicate of http://stackoverflow.com/questions/2113795, and paxdiablo's answer is wrong, as Reid explained. Reid's algorithm is O(n) if you keep a list of which elements were in each half as you're counting. – jcd Dec 10 '10 at 14:08

3 Answers3

9

It's a mathematical property that the sum of the numbers between 1 and n where n is n(n+1)/2. You can see this for 10:

  1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10
= (1+10) + (2+9) + (3+8) +(4+7) + (5+6)
= 11 + 11 + 11 + 11 + 11
= 55

So, by extension, is the sum of the numbers from 0 thru n since you're just adding 0 to it. So what you do is add up all the numbers and maintain a count, then use that formula to figure out the missing one.

So, something like:

count = 0
sum = 0
foreach num in list:
    sum = sum + num
    count = count + 1
missing = count * (count+1) / 2 - sum

Getting the number with bit(i,j) is tricky so you'll have to extract the bits individually and turn them into actual numbers for summing.

paxdiablo
  • 854,327
  • 234
  • 1,573
  • 1,953
  • This reads all n log n bits of A, so it takes n log n time. – Reid Barton Oct 30 '10 at 14:42
  • 1
    @Reid: no, it's not n log n at all. You can't use n for both the number of bits _and_ the number of integers. The number of bits in an integer is _constant_ so it's effectively `O(32n)` (for a 32-bit number) which is exactly the same as `O(n)`. – paxdiablo Oct 30 '10 at 15:56
  • I'm pretty sure when the OP writes "integer", they mean "integer", not "integer less than 2^32". Otherwise, there are only finitely many possible inputs, so it doesn't make sense to talk about asymptotic runtime at all. Obviously the length of an actual mathematical integer in bits is not constant. – Reid Barton Oct 30 '10 at 16:43
  • I'm pretty certain that integer means a fixed-width integer be that 32-bits or 1024-bits, not a variable length one based on the value of the integer. That's because this is a programming Q&A site and the number of fixed width architectures far outweigh the number of variable width architectures :-) Whether the fixed width is 32 or any other constant, it doesn't matter, it's still a constant. I could be wrong but, based on the preponderance of evidence, I doubt it. Feel free to question the OP if you want clarification. If it turns out I'm wrong, I'll delete or edit to fix. – paxdiablo Oct 30 '10 at 16:58
7

You could use XOR operator as its faster than addition. Since you have access to each bit you will be doing a bitwise XOR here. The principle to be used here is (A XOR B XOR A ) = B

eg: (1 XOR 2 XOR 3) XOR (1 XOR 2) = 3

for i=0 to n
{
Total=Total XOR i
}

foreach element in A
{
Total=Total XOR element
}
Whimsical
  • 5,985
  • 1
  • 31
  • 39
  • Actually, that's pretty nifty, +1. You can't be _sure_ that XOR will be faster than addition but it's a neat modification to the two-of-most/one-of-one (e.g., `91 91 82 82 73 64 64 55 55`) variation that uses XOR to find the singleton. – paxdiablo Oct 28 '10 at 08:31
  • 1
    Xor will never be slower than Addition... Why : In addition there is a carryover bit which requires a full adder adding one step...It is eliminated using parallel adders in modern architecture which has almost the same performance(xor uses 1 gate lesser on this operation) – Whimsical Oct 28 '10 at 08:52
  • There is an O(1) formula for XOR of 1 to n. http://stackoverflow.com/questions/3932346/direct-formula-for-summing-xor. XOR also avoids overflow issues. –  Oct 28 '10 at 18:11
0

It's a trick question then, since using the bit method would only require that you cycle each bit for each number, meaning it would automatically become O(n*j) where j is the number of bits representing n.

I think paxdiablo's got it, assuming you're allowed a solution which doesn't use the bit method.

Neil
  • 5,762
  • 24
  • 36
  • 3
    Neil, that would still be technically `O(n)` since `j` is a constant. – paxdiablo Oct 28 '10 at 08:36
  • j is constant in practice because the length of an integer or long is always the same, however the significant digits of j increments by one with n*2 where n > 0. More like O(log n). – Neil Oct 29 '10 at 09:56