Last Updated: 9 Sep, 2021
Minimum Swapping
Moderate
Asked in companies
You are given an array ‘arr’ of size ‘N’ containing 0 and 1. You can swap any two adjacent elements. Your task is to find the minimum number of swaps such that the 0 are shifted to one side, and 1 shifted to the other.
For example:
For the given array ‘arr’ = {1,0,1,1} we can swap the first and second elements, and all 1s will be shifted to the right side and 0s to the left side. Hence a minimum number of operations required is 1.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows.
The first line of each test case contains an integer ‘N’, denoting the size of the array.
The second line of each test case contains ‘N’ space-separated integers representing the elements of the array.
Output Format :
For each test case, print the minimum number of swaps required to arrange 0 to one side and 1 to the other side.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= N <= 10^6
0 <= arr[i] <= 1
Time limit: 1 sec
Approaches
We will try to push all the 1s towards the left side.
After that, we will try to push all the 1s towards the right side.
The minimum number of swaps required in both cases will be our answer.
Algorithm :
- Maintain two pointers, ‘left’ and ‘right’. Initialize both of them to 0.
- We will also be maintaining ‘ans1’ and ‘ans2’ and initialize them to 0.
- Run a for loop from i = ‘right’ to ‘N’, and whenever the value of arr[right] equals 0, then we will continue.
- Otherwise,
- We will count the number of zeros behind and add them to our answer
- We will run a for loop from j = ‘i’-1 to 0 by decrementing the value of j.
- If arr[j] equals 0, then
- Increment the answer by 1.
- Else,
- Break from the loop.
- In this way, we are trying to push all the 1s to the left side
- Now we will try to push all the 1s to the right side.
- Initialize right with ‘N’ -1 and left with ‘N’-1
- Run a for loop from ‘i’ = right to 0, by decrementing the value of i.
- If arr[i] equals 0, then we will continue.
- Else,
- We will count the number of zeros ahead and add them to our answer.
- We will run a loop from ‘j’ = i+1 to ‘N’,
- If arr[j] equals 0, then we will increment our answer by 1,
- Otherwise, we will break from the loop.
- Return the minimum answer obtained in both cases.
Again, we will try to push all the 1s towards the right side and count the number of operations. And after that, we will try to push 1s towards the right and count the number of operations. Minimum of both is going to be our answer.
Algorithm:
- Maintain two pointers, ‘left’ and ‘right’. Initialize both of them to 0.
- We will also be maintaining ‘ans1’ and ‘ans2’ and initialize them to 0.
- Run a for loop from i = ‘right’ to ‘N’, and whenever the value of arr[right] equals 0, then we will continue.
- Otherwise,
- We will count the number of zeros behind and add them to our answer
- We will run a for loop from j = ‘i’-1 to 0 by decrementing the value of j.
- If arr[j] equals 0, then
- Increment the answer by 1.
- Else,
- Break from the loop.
- After that, we will swap temp[left] with temp[i], and then increment left by 1.
- In this way, we are trying to push all the 1s to the left side
- Now we will try to push all the 1s to the right side.
- Initialize right with ‘N’ -1 and left with ‘N’-1
- Run a for loop from ‘i’ = right to 0, by decrementing the value of i.
- If arr[i] equals 0, then we will continue.
- Else,
- We will count the number of zeros ahead and add them to our answer.
- We will run a loop from ‘j’ = i+1 to ‘N’,
- If arr[j] equals 0, then we will increment our answer by 1,
- Otherwise, we will break from the loop.
- After that, we will swap arr[left] with arr[i] and decrement left by 1.
- Return the minimum answer obtained in both cases.