Linear algorithm on binary strings

Question

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

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 j^th 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

That doesn't sound possible; you can't know what's missing without looking at all the bits, and there are O(n log n) bits. — Oliver Charlesworth
– Oliver Charlesworth, Commented Sep 24, 2014 at 19:23
Also, given that you have the text of that PDF, please post the text, rather than an image of the text. Thanks. — Oliver Charlesworth
– Oliver Charlesworth, Commented Sep 24, 2014 at 19:24
@OliverCharlesworth You can do it if only one string is missing. — Ivan Smirnov
– Ivan Smirnov, Commented Sep 24, 2014 at 19:28
@IvanSmirnov: Yes, you're right, smart solution! (+1 to that answer) — Oliver Charlesworth
– Oliver Charlesworth, Commented Sep 24, 2014 at 19:30

Ivan Smirnov · Accepted Answer · 2014-09-24 19:40:44Z

8

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 + ... + 2¹-1 <= 2^ℓ+1 <= 2n+2 = O(n).

edited Sep 24, 2014 at 19:40

answered Sep 24, 2014 at 19:27

Ivan Smirnov

4,44521 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Ivan Smirnov Over a year ago

Oh, thanks for that <sup> tag -- I tried LaTeX markdown to write powers but it doesn't work here.

Ted Hopp Over a year ago

Just a nitpick (doesn't affect the validity of the answer): 2^(ℓ+1) = 2n + 2, so your next-to-last inequality is wrong.

Ivan Smirnov Over a year ago

@TedHopp Thanks, you're right. Fixed it. I hate those +/-1-s.

Ted Hopp Over a year ago

Actually, since you have exactly ℓ terms of -1, you can write the exact number of FetchBit calls: 2^(ℓ+1)-ℓ-1 = 2n-ℓ+1. No need for inequalities.

Collectives™ on Stack Overflow

Linear algorithm on binary strings

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related