# Even Odd Separation O(N) Single Iteration

• DSA

Given an array containing a mix of even and odd numbers, and we need to perform Even Odd Separation. In this post we’ll see how to separate even and odd numbers in a single iteration using two pointers.

## Example

``````Input: [1,3,2,5,9,4]
Output:[1 3 5 9 2 4]

Input: [8, 13, 14, 16, 17, 18, 21]
Output:[13 17 21 8 14 16 18]``````

## Method 1

To separate even-odd elements, we can take an extra array and start filling the even/odd numbers first and then the rest, but this would take a lot of time and space.

## Method 2 – Optimized O(N)

Even Odd Separation using pointers.

Separate 0s and 1s in an array, using two pointers.

First, we take two pointers – [always] and [asuwish]. Both of them start from the beginning but the [always] pointer keeps on moving irrespective of even or odd but, the [asuwish] pointer stops once it encounters an even number on the way, and increments only when it encounters an odd number.

And the swapping occurs when,

`arr[asuwish]%2==0 && arr[always]%2!=0`

I hope you got the logic, if you’re in doubt, look at the code below and perform a dry run using pen and paper. Note: The names of pointers are an example, we can change as we wish.

## Even Odd Separation Code

``````#include<iostream>
using namespace std;

int main()
{
int arr[]={12,3,5,7,9,2,4,6,8,13,14,16,17,18,21};
int asuwish, always, noe, temp, index;
noe=sizeof(arr)/sizeof(arr[0]);
for(always=0;always<noe;cout<<arr[always++]);
for(asuwish=0,always=0;always<noe;always++)
{
if(arr[asuwish]%2==0&&arr[always]%2!=0)
{
temp=arr[always];
for(index=always;index>=asuwish;index--)
arr[index]=arr[index-1];
arr[asuwish]=temp;
}
if(arr[asuwish]%2!=0)
asuwish++;
}
cout<<endl;
for(always=0;always<noe;cout<<arr[always++]<<" ");
return 0;
}``````
``````Output:
12 3 5 7 9 2 4 6 8 13 14 16 17 18 21
3 5 7 9 13 17 21 12 2 4 6 8 14 16 18``````

## Conclusion

This post is part of my #30DaysChallenge to write a blog post every day on what I learn every day, All the Best~ Abhiram Reddy.