**Problem**

Given an `array`

consisting of only `1s`

and `0s`

, your task is to `sort`

this binary array such that all `0s`

are on the `left`

and all `1s`

are on the `right`

. You are allowed to swap only adjacent elements. Find the `minimum`

number of swaps required to sort this array.

#### Input

The first line contains an integer **n**, the number of elements in array **arr[]**.

The next line contains **n** space-separated integers **arr[i]**.

#### Output

**int:** minimum number of swaps required to sort the input array

#### Sample Input

7 1 1 0 0 0 1 0

#### Sample Output

9 Explanation Input array : [1, 1, 0, 0, 0, 1, 0] 1st swap : [1, 1, 0, 0, 0, 0, 1] 2nd swap : [1, 0, 1, 0, 0, 0, 1] 3rd swap : [1, 0, 0, 1, 0, 0, 1] 4th swap : [1, 0, 0, 0, 1, 0, 1] 5th swap : [1, 0, 0, 0, 0, 1, 1] 6th swap : [0, 1, 0, 0, 0, 1, 1] 7th swap : [0, 0, 1, 0, 0, 1, 1] 8th swap : [0, 0, 0, 1, 0, 1, 1] 9th swap : [0, 0, 0, 0, 1, 1, 1]

#### Solution

**Approach:** **Greedy Approach **

The idea is to traverse the array in reverse from the **n-1th index** to the **0th index** and maintain a variable **currOnePos** (**initialised** as **n-1**), saving the current position of the sorted **left-most** **1**. We will keep updating the variable **currOnePos** as we’ll encounter **1** in the array, and add the difference between the **index of the encountered 1** and **currOnePos** to the required **answer**.

```
//
// main.cpp
// Sort Binary Array
//
// Created by Himanshu on 06/04/22.
//
#include <iostream>
using namespace std;
int solve (int arr[], int n) {
int ans = 0;
int currOnePos = n-1;
for (int index=n-1; index>=0; index--) {
if (arr[index] == 1) {
ans += currOnePos-index;
currOnePos--;
}
}
return ans;
}
int main() {
int n;
cin>>n;
int *arr = new int[n]();
for (int i=0; i<n; i++) {
cin>>arr[i];
}
cout<<solve(arr, n)<<endl;
return 0;
}
```

**Time complexity: O(n)**, where n is the size of array

**Here’s a working example:**

https://ideone.com/ZfoA5Y