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
    for j in [start, start + 1, ..., end]:
        if A[j][i] = 0:
            actual_0s += 1
        else:
            actual_1s += 1

    if actual_0s < expected_0s:
        return find_missing_recursive(i - 1, start, start + expected_0s - 1, A)
    else:
        return find_missing_recursive(i - 1, start + expected_0s, end, A) 

Example

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

We can now walk through the algorithm:

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

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

    actual_0s = 4
    actual_1s = 2

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

               actual_0s = 1
               actual_1s = 1

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

                          actual_0s = 1
                          actual_1s = 0

                          return find_missing_recursive(0, 5, 5, [0,1,2,3,4,6]):
                                     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.