Minimum Swaps required to group all 1’s together

Given an array arr[] consisting of binary digits 0 and 1, determine the minimum number of swaps to push 0s towards one end and 1s to the other end of the array. Swapping of only adjacent elements is allowed.

Examples:

Input : arr={0, 1, 0, 1}
Output : 1
We can get {0, 0, 1, 1} by swapping binary digits at indexes 1 & 2.

Input : arr={1, 1, 1, 1, 0, 1, 0, 1}
Output : 3 
We can get {1, 1, 1, 1, 1, 1, 0, 0} by swapping binary digits at indexes 
4 & 5 and then swapping elements at indexes 6 & 7 and 5 & 6.

Approach:
The idea is to find number of moves to get 1s at left end and number of moves to get 1 at right end of the array. Minimum of both the values is the answer.
Below are the detailed steps:

Maintain a count1 variable to find number of swaps to get 1s at the left end.
Initialise count to zero and do this every arr[i]
If arr[i]=1, then find number of zeros to the left and add to count1.
Maintain a count2 variable to find number of swaps to get 1s at the right end. Initialise it to zero and do this for every arr[i]:
If arr[i]=1, then find number of zeros to the right and add to count2.
Return minimum of count1 and count2.

Below is the implementation of the above algorithm:

C++

// C++ program to find the minimum number of swaps 
// to get 0s at one end and 1s at the other end. 
#include <bits/stdc++.h>
using namespace std;

// Function to find the minimum number of swaps 
// to get 0s at one end and 1s to the other end. 
int getMinimumSwaps(int size, int arr[]) {
    int zerosTowardsLeft = 0, zerosTowardsRight = 0;
    int count1 = 0, count2 = 0;

    // Loop to count the number of swaps 
    // to get 1s at the left end 
    // and 0s at the right end. 
    for (int i = 0; i < size; i++) {
        if (arr[i] == 1) {
            count1 += zerosTowardsLeft;
        } else {
            zerosTowardsLeft++;
        }
    }

    // Loop to count the number of swaps 
    // to get 1s at the right end 
    // and 0s at the left end. 
    for (int i = size - 1; i >= 0; i--) {
        if (arr[i] == 1) {
            count2 += zerosTowardsRight;
        } else {
            zerosTowardsRight++;
        }
    }

    // Returning the minimum of both counts.
    return min(count1, count2);
}

// Driver program
int main() {
    int arr[] = {1, 1, 1, 1, 0, 1, 0, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << getMinimumSwaps(n, arr) << endl;

    return 0;
}

Java

// Java program to find the minimum number of swaps 
// to get 0s at one end and 1s at the other end. 
public class GFG {
    // Function to find the minimum number of swaps 
    // to get 0s at one end  and 1s at the other end. 
    static int getMinimumSwaps(int size, int arr[]) {
        int zerosTowardsLeft = 0, zerosTowardsRight = 0;
        int count1 = 0, count2 = 0;
        
        // Loop to count the number of swaps 
        // to get 1s at the left end and 0s  at the right end. 
        for (int i = 0; i < size; i++) {
            if (arr[i] == 1) {
                count1 += zerosTowardsLeft;
            } else {
                zerosTowardsLeft++;
            }
        }

        // Loop to count the number of swaps to 
        // get 1s at the right end and 0s at the left end. 
        for (int i = size - 1; i >= 0; i--) {
            if (arr[i] == 1) {
                count2 += zerosTowardsRight;
            } else {
                zerosTowardsRight++;
            }
        }
        // Returning the minimum of both counts.
        return Math.min(count1, count2);
    }

    // Driver program
    public static void main(String args[]) {
        int arr[] = {1, 1, 1, 1, 0, 1, 0, 1};
        int n = arr.length;

        System.out.println(getMinimumSwaps(n, arr));
    }
}

Output:

Time Complexity: O(n)
Space Complexity: O(1)

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.