Given an array of even and odd numbers. We have to move all the odds to the start and then all then even of the end maintaining the relative order of numbers. Found one solution but don't know which algorithm is this. Can anyone help me know which algorithm this solution uses?
Interviewer wanted me to do it in O(N) Time and O(1) space.
The Idea is to count total odd numbers, then move even numbers one by one to correct position.
void segregateEvenOdd(int arr[], int n) {
int countOdd = 0;
for (int i = 0; i < n; i++) {
if (arr[i] % 2 != 0) {
countOdd++;
}
}
int i = 0, j = i + 1;
while (i != countOdd) {
if (arr[i] % 2 == 1) {
i++;
j = i + 1;
}
else if (arr[i] % 2 == 0 && j < n) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
j++;
}
}
}e.g.:
Input: [2, 3, 7, 4, 6, 1]
Output: [3, 7, 1, 2, 4, 6]
Comments (1)