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]
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]
Solution :
Find the wrong positions for 0 and 1 and swap them
Complexity :- Time : O(N)
- Space : O(1)
void interleave_0_1(int input[], int N){
int i=0, j=1;
while(1){
}while(1){
while(i < N && input[i] == 0)
while(j < N && input[j] == 1)
if(i < N && j < N){
else
}
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];
}input[j] ^= input[i];
input[i] ^= input[j];
else
break;
No comments:
Post a Comment