Wednesday, March 11, 2009

An array of N bits, split in two parts with same amout of bits set to one

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.


  1. Since 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.

    Best 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.

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

    By 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?