Saturday, September 24, 2022
HomeSoftware DevelopmentReduce strikes to segregate even and odd by swapping adjoining parts

Reduce strikes to segregate even and odd by swapping adjoining parts


Given an array arr[] of dimension N, the duty is to search out the minimal strikes to segregate even and odd numbers by swapping two adjoining parts at a time.

Instance:

Enter: N = 7, arr = {3, 5, 2, 7, 9, 11, 12}
Output: 3
Clarification: Swap arr[2] and arr[3] to get arr = {3, 5, 7, 2, 9, 11, 12}.
Transfer 2: Swap arr[3] and arr[4] to get arr = {3, 5, 7, 9, 2, 11, 12}.
Transfer 3: Swap arr[4] and arr[5] to get arr = {3, 5, 7, 9, 11, 2, 12}.
All odds are in the beginning from arr[0 . . . 4] 
and evens on the finish from arr[5 . . . 6].

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

 

Method:

This drawback could be damaged down into two sub-problems: 

  • Shifting all odd to the entrance or 
  • shifting all odd to the top (minimal of which is able to give us the optimum reply). 

So this drawback could be solved utilizing the grasping strategy, the place initially the variety of strikes to shift odd to the begining are counted after which the variety of strikes to shift odd to the top are counted and minimal of each is returned as reply.

To shift any quantity by consecutive swapping, strikes required is abs(j – i) the place j is the index of the final variety of the other parity and i is the index of the present quantity. 

Comply with the given steps to resolve the issue:

  • 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 minimal of startMoves and endMoves as the ultimate reply.

Beneath is the implementation of this strategy:

C++14

  

#embrace <bits/stdc++.h>

utilizing 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 fundamental()

{

    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 House: O(1)

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular