[Solved]: Fastest Algo to separate the 0s and 1s

Problem Detail: 

Suppose, I have an array of length 100. I have 0s at some positions and 1s at some other positions. What is the fastest method by which I can separate the 0s and 1s, so that we get all the 0s at the beginning and all the 1s at the remaining positions / vice-versa?

Asked By : Raj Wadhwa

Answered By : saadtaame

Here is another version of Yuval's algorithm that uses two loops only.

int number_of_ones = 0; for(int i = 0; i < 100; ++ i) {   number_of_ones += A[i];     A[i] = 0; } for(i = 100 - number_of_ones; i < 100; ++ i) {   A[i] = 1; } 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10598

3.2K people like this

 Download Related Notes/Documents