patternMinor
Find The missing number in range [0,n]
Viewed 0 times
findnumbertherangemissing
Problem
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.
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.
Solution
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)$.
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)$.
Context
StackExchange Computer Science Q#25841, answer score: 7
Revisions (0)
No revisions yet.