Hello Everyone,
Given an array of integers, segregate even and odd numbers in the array. All the even numbers should be present first, and then the odd numbers.
Examples:
Input: arr = 1 9 5 3 2 6 7 11
Output: 2 6 5 3 1 9 7 11Input: arr = 1 3 2 4 7 6 9 10
Output: 2 4 6 10 7 1 9 3
Brute-Force Solution
As we need to maintain the order of elements then this can be done in the following steps :
- Create a temporary array A of size n and an integer ind which will keep the index of elements inserted .
- Initialize ind with zero and iterate over the original array and if even number is found then put that number at A[ind] and then increment the value of ind .
- Again iterate over array and if an odd number is found then put it in A[ind] and then increment the value of ind.
- Iterate over the temporary array A and copy its values in the original array.
// C++ Implementation of the above approach
#include <iostream>
using namespace std;
void arrayEvenAndOdd( int arr[], int n)
{
int a[n], ind = 0;
for ( int i = 0; i < n; i++)
{
if (arr[i] % 2 == 0)
{
a[ind] = arr[i];
ind++;
}
}
for ( int i = 0; i < n; i++)
{
if (arr[i] % 2 != 0)
{
a[ind] = arr[i];
ind++;
}
}
for ( int i = 0; i < n; i++)
{
cout << a[i] << " " ;
}
cout << endl;
}
// Driver code
int main()
{
int arr[] = { 1, 3, 2, 4, 7, 6, 9, 10 };
int n = sizeof (arr) / sizeof ( int );
// Function call
arrayEvenAndOdd(arr, n);
return 0;
}
Output
2 4 6 10 1 3 7 9
Time complexity: O(n)
Auxiliary space: O(n)