Friday, August 15, 2008

Small programming pblm ...

Given an array contains 0s and 1s mixed together, in one scan of the whole array, is it possible to put all the 0s on the left and all the ones to the right ?

I got the solution (I think) :-) But I took sometime.

4 comments:

Tejaswi said...

Do you mean a single pass in the strict sense? or a O(N) solution good enough. If so, a simple quick sort partition algorithm will work.

-T

sudeep said...

ella patternify maadta idya ..You seem to have specialized in mapping one problem to another...

Cue for my soln. :-

My "solution" involved using two pointers.

One at the beginning of the array and the other at the end of the array.

These two pointers start moving towards each other.

When these two meet each other, then the left side contains only 0s and the right side contains 1s.

GD said...

my mind works similar to sudeep's :-). I was glad that it still works about Algos.. nevertheless it is basic stuff :-)

Yeah the question raised whether your were looking at linear or O(N) solution or strictly a single pass..

and BE boys can think straight ..
MTech boys will try and fit into a box :-).. thats the essence of masters ..yella yello fit aaga beku.. aaglilla andre verify mada beku.. and then still its unique you have a paper .. kranti aytu anta .. irli ..

richie said...

zeeds: Please restrict comment to PES->IIT Bombay students :).