CODEWITHSUNDEEP
algorithm
Collin
Collin

Reputation: 1875

Linear algorithm on binary strings

I'm going through some old midterms to study. (None of the solutions are given)

I've come across this problem which I'm stuck on

  1. Let n = 2ℓ − 1 for some positive integer ℓ. Suppose someone claims to hold an array A[1.. n] of distinct ℓ-bit strings; thus, exactly one ℓ-bit string does not appear in A. Suppose further that the only way we can access A is by calling the function FetchBit(i, j), which returns the jth bit of the string A[i] in O(1) time.
    Describe an algorithm to find the missing string in A using only O(n) calls to FetchBit.

The only thing I can think of is go through each string, convert it to base 10, sort them all and then see which value is missing. But that's certainly not O(n)

Proof it's not homework... http://web.engr.illinois.edu/~jeffe/teaching/algorithms/hwex/f12/midterm1.pdf

Upvotes: 1

Views: 1760

Answers (1)

Ivan Smirnov
Ivan Smirnov

Reputation: 4435

You can do it in 2n operations.

First, look at the first bit of every number. Obviously, you will get 2ℓ-1 zeros and 2ℓ-1-1 ones ore vice versa (because only one number is missing). If there is 2ℓ-1-1 ones then you know that the first bit of the missing number is one, otherwise it is zero.

Now you know the first bit of a missing number. Let's look at all numbers which have the same first bit (there are 2ℓ-1-1 of them) and repeat the same procedure with their second bit. This way you will determine the second bit of the missing number, and so on.

The total number of FetchBit calls will be 2ℓ-1 + 2ℓ-1-1 + ... + 21-1 <= 2ℓ+1 <= 2n+2 = O(n).

Upvotes: 8

Related Questions