Update appNew update is available. Click here to update.

Minimum Swaps to Group All 1's Together

Posted: 18 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given an array/list ‘ARR’ of size ‘N’. ‘ARR' is binary i.e. it contains only 0s and 1s (ARR[i] = {0, 1}). Your task is to find out the minimum number of swaps required to group all 1s together.

Note: If ‘ARR’ contains only 0’s then print -1.

Example:

Let ‘ARR’ = [ 0, 1, 0, 1]. We can group all 1s together in the following ways: ‘ARR’ =[0, 0, 1, 1] or ‘ARR’ = [0, 1, 1, 0]. 

In this example, we need only 1 swap to group all 1’s together which is the minimum possible. 
Input Format:
The first line of input contains an integer ‘T’ which denotes the number of test cases. 

The first line of each test case contains a single integer ‘N’ representing the number of elements in the array/list ‘ARR’.

The next line of each test case contains ‘N’ single space-separated integers (0s and 1s) denoting the elements of  ‘ARR’.
Output Format :
For each test case, return the minimum number of swaps required to group all 1’s together.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= ‘T’ <= 100
2 <= ‘N’ <= 5000
0 <= ‘ARR[i]’ <= 1

Where ‘ARR[i]’ represents the elements of array/list ‘ARR’. 

Time Limit: 1 sec