Codechef•Jul 01, 2025

Minimum number of Flips

Hazrat Ali

Codechef

Chef has an array A of length N consisting of 1 and −1 only.

In one operation, Chef can choose any index i (1≤i≤N) and multiply the element Ai by −1.

Find the minimum number of operations required to make the sum of the array equal to 0. Output -1 if the sum of the array cannot be made 0.

Input Format

  • First line will contain T, number of test cases. Then the test cases follow.
  • First line of each test case consists of a single integer N denoting the length of the array.
  • Second line of each test case contains N space-separated integers A1,A2,…,AN denoting the array A.

Output Format

For each test case, output the minimum number of operations to make the sum of the array equal to 0. Output -1 if it is not possible to make the sum equal to 0.

Constraints

  • 1≤T≤100
  • 2≤N≤1000
  • Ai=1 or Ai=−1

Sample 1:

Input 
4
4
1 1 1 1
5
1 -1 1 -1 1
6
1 -1 -1 1 1 1
2
1 -1

Output
2
-1
1
0

Solution

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    if n % 2 == 1:
        print(-1)
        return

    positive = sum(1 for x in a if x == 1)
    negative = n - positive
    half = n // 2

    print(min(abs(half - positive), abs(half - negative)))


T = int(input())
for _ in range(T):
    solve()




 

Comments