How to partition bits in a bit array with less than linear time
Posted
by SiLent SoNG
on Stack Overflow
See other posts from Stack Overflow
or by SiLent SoNG
Published on 2010-03-17T07:08:07Z
Indexed on
2010/03/17
7:11 UTC
Read the original article
Hit count: 249
This is an interview question I faced recently.
Given an array of 1 and 0, find a way to partition the bits in place
so that 0's are grouped together, and 1's are grouped together. It does not matter whether 1's are ahead of 0's or 0's are ahead of 1's.
An example input is 101010101
, and output is either 111110000
or 000011111
.
Solve the problem in less than linear time.
Make the problem simpler. The input is an integer array, with each element either 1 or 0. Output is the same integer array with integers partitioned well.
To me, this is an easy question if it can be solved in O(N). My approach is to use two pointers, starting from both ends of the array. Increases and decreases each pointer; if it does not point to the correct integer, swap the two.
int * start = array;
int * end = array + length - 1;
while (start < end) {
// Assume 0 always at the end
if (*end == 0) {
--end;
continue;
}
// Assume 1 always at the beginning
if (*start == 1) {
++start;
continue;
}
swap(*start, *end);
}
However, the interview insists there is a sub-linear solution. This makes me thinking hard but still not get an answer.
Can anyone help on this interview question?
© Stack Overflow or respective owner