array of 0's and 1's. keep 0 at even and 1 at odd places

by manojgumber

Q .
You are given an array of integers containing only 0s and 1s. you have to place all the 0s in even position and 1s in odd position and if suppose no if 0s exceed no. of 1s or vice versa then keep them untouched. Do that in ONE PASS and WITHOUT taking EXTRA MEMORY.

input array:
{0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 }
output array:
{0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 }

A.
This is similar to an implementation of partition method of quick sort.We start from the left and keep two index one for even position and other for odd positions. Traverse these index from left. At even position there should be 0 and At odd positions, there should be 1’s . Whenever there is mismatch , we swap the values at odd and even index.


void
arrangeArray (int a[], int size)
{
oddInd = 1;
evenInd = 0;
while (true)
{
while (evenInd < size && a[evenInd] == 0)
evenInd += 2;
while (oddInd < size && a[oddInd] == 1)
oddInd += 2;
if (evenInd < size && oddInd < size)
swap (a[evenInd], a[oddInd])
else
break;
}

}
 
Advertisements