# Segregate even and odd numbers in minimum time complexity

Here, we are going to learn how to segregate even and odd numbers in minimum time complexity from an array of integers?
Submitted by Radib Kar, on November 13, 2018

Problem statement:

Given an array of integers. Write a function to segregate the Even and Odd numbers. Put the even numbers first.

Solution:

Algorithm:

1. Set two index variable, left = 0 and right = n-1 (n = array length)
2. Keep increasing the left index until any odd no is found.
3. Keep decreasing the right index until any even no is found.
4. If left < right, swap array[left] and array[right].

Time complexity: O(n) (only one scan )

Space complexity: O(1) (no additional space used)

Comment: The input order can be changed in the output as we are swapping on local observation.

## C++ implementation to Segregate even and odd numbers in minimum time complexity

```#include <bits/stdc++.h>
using namespace std;

void print(int* a,int n){
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
cout<<endl;
}

void swap(int* a,int* b){
int temp;
temp=*a;
*a=*b;
*b=temp;
}

void separate(int* a, int n){
int left=0,right=n-1;
while(left<right){
// increment left until any odd no is found
while(a[left]%2==0 && left<right)
left++;
// increment right until any even no is found
while(a[right]%2==1 && left<right)
right--;
if(left<right){
//swap array[left] & array[left] using pointer to reference
swap(&a[left],&a[right]);
left++;
right--;
}
}
}

int main(){
int n;
// enter array length
cout<<"enter no of elements\n";
cin>>n;
int* a=(int*)(malloc(sizeof(int)*n));
//fill the array
cout<<"enter elements...\n";
for(int i=0;i<n;i++)
scanf("%d",&a[i]);

cout<<"array before segregating...\n";
print(a,n);
cout<<"array after segregating...\n";
separate(a,n);
print(a,n);

return 0;
}
```

Output

```enter no of elements
8
enter elements...
11
12
13
67
66
45
34
38
array before segregating...
11 12 13 67 66 45 34 38
array after segregating...
38 12 34 66 67 45 13 11
```

TOP Interview Coding Problems/Challenges

Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.
Learn PCB Designing: PCB DESIGNING TUTORIAL

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.