Select Page

Minimize moves to segregate even and odd by swapping adjacent elements

Team 1 - Programming
Published: August 9, 2022

Given an array arr[] of size N, the task is to find the minimum moves to segregate even and odd numbers by swapping two adjacent elements at a time.

Example:

Input: N = 7, arr = {3, 5, 2, 7, 9, 11, 12}
Output: 3
Explanation: Swap arr[2] and arr[3] to get arr = {3, 5, 7, 2, 9, 11, 12}.
Move 2: Swap arr[3] and arr[4] to get arr = {3, 5, 7, 9, 2, 11, 12}.
Move 3: Swap arr[4] and arr[5] to get arr = {3, 5, 7, 9, 11, 2, 12}.
All odds are at the beginning from arr[0 . . . 4] 
and evens at the end from arr[5 . . . 6].

Input: N = 5, arr = {3, 5, 7, 2, 4}
Output: 0

 

Approach:

This problem can be broken down into two sub-problems: 

  • Shifting all odd to the front or 
  • shifting all odd to the end (minimum of which will give us the optimal answer). 

So this problem can be solved using the greedy approach, where initially the number of moves to shift odd to the begining are counted and then the number of moves to shift odd to the end are counted and minimum of both is returned as answer.

To shift any number by consecutive swapping, moves required is abs(j – i) where j is the index of the last number of the opposite parity and i is the index of the current number. 

Follow the given steps to solve the problem:

  • Traverse the array arr from 0 to n-1 (say i).
    • If arr[i] is odd then add i-j in startMoves and increment j.
    • Reinitialize j to n-1.
  • Traverse the array arr from n-1 to 0 (say i).
    • If arr[i] is odd then add j-i to endMoves and decrement j.
  • Return minimum of startMoves and endMoves as the final answer.

Below is the implementation of this approach:

C++14

  

#include <bits/stdc++.h>

using namespace std;

  

int minMovesToSegregate(int* arr, int& n)

{

    int startMoves = 0, endMoves = 0, j = 0;

    for (int i = 0; i < n; i++) {

        if (arr[i] & 1)

            startMoves += i - (j++);

    }

    j = n - 1;

    for (int i = n - 1; i >= 0; i--) {

        if (arr[i] & 1)

            endMoves += (j--) - i;

    }

    return min(startMoves, endMoves);

}

  

int main()

{

    int arr[] = { 3, 5, 2, 7, 9, 11, 12 };

    int N = sizeof(arr) / sizeof(arr[0]);

  

    

    cout << minMovesToSegregate(arr, N);

    return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1)

Source: www.geeksforgeeks.org