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