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!

Improve this question
4
  • If bit(i,j) is the ONLY operation available, how do you propose to implement a divide-and-conquer algorithm ? Commented Oct 28, 2010 at 7: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. Commented Oct 28, 2010 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. Commented Oct 30, 2010 at 14:46
  • This isn't a duplicate of 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. Commented Dec 10, 2010 at 14:08

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

This reads all n log n bits of A, so it takes n log n time.
@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).
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.
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.
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
}
Improve this answer

3 Comments

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.
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)
There is an O(1) formula for XOR of 1 to n. stackoverflow.com/questions/3932346/…. XOR also avoids overflow issues.
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.

Improve this answer

2 Comments

Neil, that would still be technically O(n) since j is a constant.
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).

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.