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.

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.

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 algorithm that finds the missing number in O(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.