# Find The missing number in range [0,n]

Given Array $$A$$ of size $$n$$ that contains all the integer values $$[0,n]$$ except one.

In this question we assume that the time we need to check one bit $$j$$ in number $$A[i]$$ is $$O(1)$$,and to check the number $$A[i]$$ is $$O(\log n)$$.

Find an algorithm that finds the missing number in $$O(n)$$.

So creating a trivial counter array and searching for a 0 count wouldn't help - it would be $$O(\log n)$$.

I also thought about counting the bits and finding the missing one, but that wouldn't help either.

• Can you clarify what u meant by "counting the bits and finding the missing one" - is it the same solution I outlined? Commented May 17, 2014 at 18:09

Compare all the Least Significant bits, and either there are less ones or zeroes.

We continue this search only on the set where there is less of some bit, half the input at each iteration.

$$n + \frac{1}{2}n + \frac{1}{4}n + ... < 2n.$$

And we accumulate the missing bits at each step, to come to the missing number.

So the running time is $O(n)$.

• I might be too stupid, but I don't really understand your answer. Commented Dec 16, 2016 at 18:07
• I'm not convinced this works. Let's say $n=4$ and $A = [0, 1, 2, 3]$ (thus 4 is missing). Then the least significant bits are $[0, 1, 0, 1]$. Presumably you'd have to take it one step further to $[00, 01, 10, 11]$, but you can't tell if $00$ is a 0 or a 4 until the very end, thus taking $O(n \log n)$ overall. You could do this for any $n = 2^k$.
– ryan
Commented May 18, 2020 at 14:26
• The logical fix for this issue would be to say "Well, check the least significant bit, then the most, then back to 2nd least, then back to 2nd most, etc." but you could get around this with $n=6$ and $A = [0, 1, 3, 4, 5, 6]$. Then for our bits we have $[000, 001, 011, 100, 101, 110]$. For least significant we have $[0, 1, 1, 0, 1, 0]$ (equal) then for most we have $[0, 0, 0, 1, 1, 1]$ (equal) and we'd have to check the bits in the middle thus making it $O(n \log n)$.
– ryan
Commented May 18, 2020 at 16:01
• I believe you can make an adversarial argument to "hide" the deciding bit in the last "row" of bits that is checked. Although, I don't know if you can do this for arbitrary $n$ which is where my argument gets stuck.
– ryan
Commented May 18, 2020 at 16:03
• You can make this argument for all $n= 2^k - 2$. You can do it by making the missing number either $0$ or $2^i$ where $i$ is the last row of bits that is checked. For example, if $n = 62 = 2^6 - 2$ so we have 6 bits to check for each number. Let's say we check the row of bits for each number in the order of 0, 5, 4, 1, 2, so that 3 is the last row that hasn't been checked. That means it is still undecided whether the missing value is either $0$ or $2^3 = 8$ until the last row of bits is checked because they are identical up to that point: $000000$ or $001000$.
– ryan
Commented May 18, 2020 at 16:15

Perhaps I am missing the point but this seems trivial.

var previousBit = 1;

for index = 0 to n -1 // -1 because the array is one short of n.
begin
var currentBit = A[index].bit(0)
if(currentBit == previousBit)
break;
else
previousBit = currentBit
end

print "missing number is ", index


Assuming A[index].bit(0) gives the zero-th bit of the number at the array position index.

This is plainly O(n)

This would be based on the observation that the least significant bit of the number toggles as you increase from 0 to n, and where it doesn't you have found the missing number.

• The numbers aren't in sorted order. Commented May 18, 2014 at 8:40
• If they were, we could do a binary search, comparing the current element with the expected number, and if there was a shift, search where appropriate. Commented May 18, 2014 at 9:45

This is similar to NightRa's answer, but I believe they were missing a few details. Simply following which Least Significant Bits there are less of will not get you to the correct solution.

You need to follow which bit has fewer than you expect.

For example, let's say $$n = 6$$ and $$A = [0, 1, 3, 4, 5, 6]$$.

Our bits are:

0 - 000
1 - 001
3 - 011
4 - 100
5 - 101
6 - 110


Our least significant bits are [0, 1, 1, 0, 1, 0], which have an equal amount of both 0 and 1 bits. However, since we know $$n=6$$, from $$0$$ to $$6$$ we expect there to be 4 even numbers (0, 2, 4, 6) and 3 odd numbers (1, 3, 5).

This means, of the least significant bits, we expect there to be 4 even bits (0) and 4 odd bits (1). We can see there are not 4 even bits, but rather only 3, so we recurse on those, going to the next least significant bit.

It's more clear to me how we can determine the expected number of bits if we start with the Most Significant Bits rather the Least Significant. The most significant bits will give us a range ([0, 3] for 0 and [4, 6] for 1 in the prior example), where as the least significant will give us even or odds ([0, 2, 4, 6] for 0 and [1, 3, 5] for 1 in the prior example) which will be trickier when you recurse.

### Algorithm

For simplicity I'm assuming we can simply "index" into the value in $$A$$ to determine the value of it's $$i$$th bit. For example if $$A = [5]$$ then $$A[0][0] = 1$$, $$A[0][1] = 0$$ and $$A[0][2] = 1$$.

find_missing(n, A):
# number of bits in n
bits = floor(log2(n) + 1)
return find_missing_recursive(bits, 0, n, A)

find_missing_recursive(i, start, end, A):
if start = end:
# We've found our missing value
return start

expected_0s = 2^(i - 1)
expected_1s = (end - start) - expected_0s + 1

actual_0s = 0
actual_1s = 0
A_0s = []
A_1s = []
for j in [0, 1, ..., length(A) - 1]:
if A[j][i] = 0:
actual_0s += 1
A_0s.append(A[j])
else:
actual_1s += 1
A_1s.append(A[j])

if actual_0s < expected_0s:
# Recurse on the 0s
return find_missing_recursive(i - 1, start, start + expected_0s - 1, A_0s)
else:
# Recurse on the 1s
return find_missing_recursive(i - 1, start + expected_0s, end, A_1s)


### Example

Let $$n = 6$$ and $$A = [3, 0, 2, 6, 4, 1]$$ (5 is missing).

We can now walk through the algorithm:

find_missing(6, [3,0,2,6,4,1]):
# number of bits in n
return find_missing_recursive(3, 0, 6, [3,0,2,6,4,1])

find_missing_recursive(3, 0, 6, [3,0,2,6,4,1]):
expected_0s = 4
expected_1s = 6 - 4 + 1 = 3

actual_0s = 4
actual_1s = 2
A_0s = [3,0,2,1]
A_1s = [6,4]

# Recurse on the 1s
return find_missing_recursive(2, 4, 6, [6,4]):
expected_0s = 2
expected_1s = 2 - 2 + 1 = 1

actual_0s = 1
actual_1s = 1
A_0s = [4]
A_1s = [6]

# Recurse on the 0s
return find_missing_recursive(1, 4, 5, [4]):
expected_0s = 1
expected_1s = 1

actual_0s = 1
actual_1s = 0
A_0s = [4]
A_1s = []

return find_missing_recursive(0, 5, 5, []):
return 5


Thus 5 is returned which is indeed the missing value.

### Analysis

The complexity for find_missing_recursive is:

$$T(n) = \begin{cases} c & n = 1\\ T(2^{\lceil \log_2(n) - 1\rceil}) + c n + c \log_2 n & n > 1 \end{cases}$$

If we assume $$n = 2^k$$ this becomes simpler:

$$T(n) = \begin{cases} c & n = 1\\ T(n / 2) + c n + c \log_2 n & n > 1 \end{cases}$$

This then evaluates to:

\begin{align} T(n) &= T(n / 2) + c n + c \log_2 n\\ &= T(n/4) + c 3n/2 + 2c \log_2 n - c\\ &= T(n/8) + c 7n/4 + 3c \log_2 n - 3c\\ &= \vdots\\ &< T(1) + 2cn + c(\log_2n)^2 - c2^{\log_2n}\\ &= cn + c(\log_2n)^2 + c\\ &= O(n) \end{align}

You can also prove this bound by induction.