Find The missing number in range [0,n]

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.