You are given an array A of N bits. I tell you that K << N are set to one, and the remaining are set to 0. You don't know what bits are set to one and what are not. You just know the amount.

What is the optimal time and space complexity to split the array in two parts such that the number of bit set to one are equal in both the parts? The two parts may be or many not be contiguous. In the latter case, you can provide two sets of indexes for A as answer.

select k random bits...

ReplyDeleteSince you don't know where bits-ONE are you gotta look everywhere linearly. You need one variable to count the bits you've found and another one to index your position inside the bit array. Run the array until the count is equal to K/2 (or the bit-ZERO count is (N-K)/2). By that time your index will point to the joint splitting the array in equal number of bits-ONE.

ReplyDeleteBest case: K/2 lookups

Worst case: N - K/2 lookups

average: N/2 (or N/2-k/4 if the worst case is N-K)

Space required: N bits + 1 counter + 1 index.

Create a subset S1 of A, by selecting K random bits. Define S2 = A - S1

ReplyDeleteBy construction in S1 you have:

+ K - t (0<=t<=K) bits set to 1

+ t (0<=t<K) bits set to 0

By construction in S2 you have:

+ K-t (0<=t<=K) bits set to 0

+ t (0<=t<K) bits set to 1

what is the next step?