Minimum Swapping

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
8 upvotes
Asked in companies
AdobeCdk global

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4
1 0 1 1
3
0 1 1
Sample Output 1 :
1
0
Explanation For Sample Output 1 :
For test case 1 :
You can swap the first and second elements in order to shift all 1 to one side and 0 to the other.

For test case 2 :
In the given array, 0 and 1 are already on the opposite side. Hence no operations are required.
Sample Input 2 :
2
5
1 0 0 1 1
6
0 0 0 1 0 0
Sample output 2 :
2
2
Hint

Try to find the minimum operation required to push all the 1s towards the left and right.

Approaches (2)
Brute Force

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.
Time Complexity

O(N^2), where ‘N’ is the length of the array ‘arr’.

 

At each index, we are going back to count the number of 0s. Hence the overall time complexity is O(N^2).

Space Complexity

O(N), where ‘N’ is the length of the array ‘arr’.

 

Since we have maintained a temporary array of size ‘N’, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Minimum Swapping
Full screen
Console