Blog # 69 : Repositioning 0 and 1

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. of 0s exceed no. of 1s or vice versa then keep the exceeding integers untouched. Do that in ONE PASS and without taking extra memory (modify the array in-place). For Example : 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] Click here to see the solution. p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice. Courtesy: Vibhaj Remarks: No remarks this time. Hit again for hints. Hints: Find the wrong positions for 0 and 1 and swap them. Hit again for solution. Solution: Complexity: 1. Time : O(N) 2. Space : O(1) Code: void interleave_0_1(int input[], int N){ int i=0, j=1; while(1){ while(i < N && input[i] == 0) i += 2; while(j < N && input[j] == 1) j += 2; if(i < N && j < N){ input[i] ^= input[j]; input[j] ^= input[i]; input[i] ^= input[j]; } else break; } }