# Move 0/1 InArray

Given an array containing only 0 and 1 as its elements. We have to sort the array in such a manner that all the ones are grouped together and all the zeros are grouped together. The group of ones can be either at the start of the array or at the end of the array. The constraint while sorting is that every one/zero can be swapped only with its adjacent zero/one. Find the minimum number of moves to sort the array as per the description.

Example:\
input array ={0,1,0,1}\
Final array = {0,0,1,1}\
Minimum moves = 1 (1 at index 1 is swapped with 0 at index 2)

input array = { 1101}\
Final array - {1110}\
Minimum moves = 1 {1 at index 2 is swapped with index 3}

Example 3:\
{1,0,0,1,0,1,1,0,0,1}\
Minimum moves = 8

**Solution:**

**Version 1: O(n^2)**

Say we are sorting with 0s first and then 1s. So, if the element in position `i` is 1 then the number of swaps required is number of 0s to it's right\
Same for 1s first and then 0s.\
So we traverse from the right and get the total number of swaps for each case and return the minimum.

```
int minSwaps(int arr[]) {
return Math.min(getMinSwapFor(arr, 0), getMinSwapFor(arr, 1));
}

int getMinSwapFor(int arr[], int num) {
    int len = arr.length;
    int totalNumberOfSwaps = 0, currNumberOfSwaps = 0;
    for (int i = len-1; i >= 0; i--) {
        if (arr[i] == num) {
            currNumberOfSwaps++;
        } else {
            totalNumberOfSwaps += currNumberOfSwaps;
        }
    }
    return totalNumberOfSwaps;
}
```

\
<https://www.geeksforgeeks.org/minimum-swaps-required-group-1s-together/>\
similar as LC 1151:


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://junnie.gitbook.io/amazon-mock-interview/2022/oa/move-0-1-inarray.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.