Non-Negative Product Codechef Solution

Problem

Alice has an array of $N$ integers — A_1, A_2, \ldots, A_NA1​,A2​,…,AN​. She wants the product of all the elements of the array to be a non-negative integer. That is, it can be either $0$ or positive. But she doesn’t want it to be negative.

To do this, she is willing to remove some elements of the array. Determine the minimum number of elements that she will have to remove to make the product of the array’s elements non-negative.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
  • The first line of each test case contains a single integer $N$ — the number of elements in the array originally.
  • The next line contains $N$ space-separated integers — A_1, A_2, \ldots, A_NA1​,A2​,…,AN​, which are the original array elements.

Output Format

For each test case, output on a new line the minimum number of elements that she has to remove from the array.

Constraints

Sample 1:

4
3
1 9 8
4
2 -1 9 100
4
2 -1 0 100
4
2 -1 -1 100

0
1
0
0

Explanation:

Test case $1$: The product of the elements of the array is $1\times 9\times 8=72$, which is already non-negative. Hence no element needs to be removed, and so the answer is $0$.

Test case $2$: The product of the elements of the array is $2\times -1\times 9\times 100=-1800$, which is negative. Alice can remove the element $-1$, and the product then becomes non-negative. Hence the answer is $1$.

Test case $3$: The product of the elements of the array is $2\times -1\times 0\times 100=0$, which is already non-negative. Hence no element needs to be removed, and so the answer is $0$.

Test case $4$: The product of the elements of the array is $2\times -1\times -1\times 100=200$, which is already non-negative. Hence no element needs to be removed, and so the answer is $0$.