Segregate even and odd numbers

Difficulty Level Easy
Frequently asked in Accolite LinkedIn MakeMyTrip Paytm
Array SortingViews 3562

Problem Statement

Suppose you have an integer array. The problem “Segregate even and odd numbers” asks to rearrange the array so that the odd and even numbers can be separated in two segments of the array. The even numbers be shifted into the left side of the array and odd numbers be shifted into the right side of the array,

Example

arr[]={ 2,4,5,1,7,8,9,7}
2 4 8 1 7 5 9 7

Explanation: All even elements are placed before odd elements Thay also follow the same order as they were in the given input.

Algorithm to Segregate even and odd numbers

1. Set i = -1, j = 0.
2. While j is not equal to n(where n is the length of the array),
    1. Check if arr[j] is even or odd if it is even
        1. Do i++, and swap the values of arr[i] and arr[j] respectively.
    2. Increase the value of j by 1.
3. Print the array.

Explanation

We have given an integer array. We are asked to rearrange the array in two parts. One part is of even numbers and other is of odd numbers. We should be doing this within the given array. Such that the even numbers should be shifted to the left side of the array. And odd numbers should be shifted to the right side of the array. For this we will be checking each of the array elements. If it is even or not, if it is even number then we will be pulling it the left side of the array. After performing this operation with even numbers. All odd number automatically will go on to the right side of the array.

Then we will traverse the array, taking two index values for a single array. One is for regular traversing and the other is for even numbers indexing. We will traverse the array with the value of j. And check if any of the numbers is even means if arr[j] is even. Then we will be swapping it with the arr[i]. We increase i only when the value of array[j] is found to be even. So that even though we do not find even valued numbers we will keep on incrementing the value of j. And then if we find the even number. Then we will swap arr[j] with arr[i] which was supposed to be an odd number.

It will only be swapped within the array when the even numbers are found. And of course, either it will be swapped with an odd number or with itself. After all these operations we will print the resultant array.

Segregate even and odd numbers

Code

C++ code to Segregate even and odd numbers

#include<iostream>

using namespace std;

void getArrangedEvenOdd(int arr[], int n)
{

    int i = -1, j = 0;
    while (j != n)
    {
        if (arr[j] % 2 == 0)
        {
            i++;
            swap(arr[i], arr[j]);
        }
        j++;
    }
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = { 2,4,5,1,7,8,9,7};
    int n = sizeof(arr) / sizeof(int);
    getArrangedEvenOdd(arr, n);
    return 0;
}

2 4 8 1 7 5 9 7

Java code to Segregate even and odd numbers

public class rearrangeEvenOdd
{
    public static void getArrangedEvenOdd( int arr[], int n)
    {

        int i = -1, j = 0;
        while (j != n)
        {
            if (arr[j] % 2 == 0)
            {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            j++;
        }
        for (int k = 0; k < n; k++)
            System.out.print(arr[k] + " ");
    }
    public static void main(String args[])
    {
        int arr[] = { 2,4,5,1,7,8,9,7};
        int n = arr.length;
        getArrangedEvenOdd (arr, n);
    }
}

2 4 8 1 7 5 9 7

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Here we have traversed the array until the index j is not equal to N. That means we traversed the array onmly once. And thus linear time complexity.

Space Complexity

O(1) as no extra space is required. The algorithm itself takes only constant space but the program as a whole takes linear space.

Translate »