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 beginning 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
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to return minimum number of swaps// required to segregate evens and oddsint 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);}// Driver codeint main(){ int arr[] = { 3, 5, 2, 7, 9, 11, 12 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call cout << minMovesToSegregate(arr, N); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG{ // Java code to implement the approach // Function to return minimum number of swaps // required to segregate evens and odds static int minMovesToSegregate(int arr[], int n) { int startMoves = 0, endMoves = 0, j = 0; for (int i = 0; i < n; i++) { if (arr[i]%2==1) startMoves += i - (j++); } j = n - 1; for (int i = n - 1; i >= 0; i--) { if (arr[i]%2==1) endMoves += (j--) - i; } return Math.min(startMoves, endMoves); } // Driver code public static void main(String[] args) { int arr[] = { 3, 5, 2, 7, 9, 11, 12 }; int N = arr.length; // Function call System.out.println(minMovesToSegregate(arr, N)); }}// This code is contributed by satwik4409. |
Python3
# Python code for the above approach# Function to return minimum number of swaps # required to segregate evens and oddsdef minMovesToSegregate(arr, n): startMoves = 0 endMoves = 0 j = 0 for i in range(0, n, 1): if (arr[i] % 2 == 1): startMoves += i - j j += 1 j = n-1 for i in range(n-1, -1, -1): if (arr[i] % 2 == 1): endMoves = endMoves + j-i j -= 1 return min(startMoves, endMoves)arr = [3, 5, 2, 7, 9, 11, 12]N = len(arr)# Function callprint(minMovesToSegregate(arr, N))# This code is contributed by lokeshmvs21. |
C#
// C# code to implement the approachusing System;public class GFG{ // Function to return minimum number of swaps // required to segregate evens and odds static int minMovesToSegregate(int []arr, int n) { int startMoves = 0, endMoves = 0, j = 0; for (int i = 0; i < n; i++) { if (arr[i] % 2 == 1) startMoves += i - (j++); } j = n - 1; for (int i = n - 1; i >= 0; i--) { if (arr[i] % 2 == 1) endMoves += (j--) - i; } return Math.Min(startMoves, endMoves); } // Driver code public static void Main(string[] args) { int []arr = { 3, 5, 2, 7, 9, 11, 12 }; int N = arr.Length; // Function call Console.WriteLine(minMovesToSegregate(arr, N)); }}// This code is contributed by AnkThon |
Javascript
<script>// Javascript code to implement the approach// Function to return minimum number of swaps// required to segregate evens and oddsfunction minMovesToSegregate(arr, n){ let startMoves = 0, endMoves = 0, j = 0; for (let i = 0; i < n; i++) { if (arr[i] & 1) startMoves += i - (j++); } j = n - 1; for (let i = n - 1; i >= 0; i--) { if (arr[i] & 1) endMoves += (j--) - i; } return Math.min(startMoves, endMoves);}// Driver code let arr = [ 3, 5, 2, 7, 9, 11, 12 ]; let N = arr.length; // Function call document.write(minMovesToSegregate(arr, N)); // This code is contributed by hrithikgarg03188. </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
