Cracking The Coding Interview/Q 5.7

From Software Engineers Wiki
Jump to: navigation, search

An array A contains all the integers from 0 to n, except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is "fetch the jth bit of A[i]," which takes constant time. Write code to find the missing integer. Can you do it in 0(n) time.

Answer

Please refer to Find a Missing Number

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox