Be Positive

Let:

• $z$ be the number of zeros.
• $m$ be the number of negative ones, meaning the number of -1 values.

A product is positive when two things are true:

1. There are no zeros in the array.
2. The number of negative factors is even.

Zeros are annoying because if even one zero exists, the whole product becomes $0$, which is not strictly positive. So every 0 must be changed. Since we can only increase values, the cheapest fix is:

$0 \to 1$

That costs $1$ operation per zero, so fixing zeros costs $z$ operations.

Now look at the -1s.

If $m$ is even, then the product of all negative values is positive. After turning all zeros into ones, the entire product is positive. Answer:

$z$

If $m$ is odd, the product is negative after fixing zeros. We need to flip one -1 into a positive number. But one operation only gives:

$-1 \to 0$

That still makes the whole product zero, which is still not positive. So we need one more operation:

$-1 \to 0 \to 1$

That costs $2$ operations. Answer:

$z + 2$

So the whole problem is just counting. Tiny math bonk, no DP dragon hiding under the bed.

Algorithm

For each test case:

1. Count zeros.
2. Count -1s.
3. Start answer as the number of zeros.
4. If the number of -1s is odd, add $2$.
5. Print the answer.

Correctness Proof

We prove the algorithm outputs the minimum number of operations.

First, every zero must be changed, because any array containing a zero has product $0$, which is not strictly positive. Since changing a zero to a nonzero value requires at least one increment, at least $z$ operations are necessary. The algorithm performs exactly these $z$ operations by changing each zero to $1$.

After all zeros are fixed, the sign of the product depends only on the number of -1 elements. If this count is even, the product is already positive, so no more operations are needed. Thus the algorithm is optimal in this case.

If the number of -1 elements is odd, the product is negative after fixing zeros. To make it positive, the parity of the number of negative elements must change. Since operations only increase values, the cheapest way to remove one negative factor is to change one -1 into 1, which takes exactly two operations: -1 -> 0 -> 1. One operation is not enough because -1 -> 0 leaves a zero in the array, making the product $0$. Therefore at least $2$ extra operations are necessary, and the algorithm performs exactly $2$ extra operations.

In all cases, the algorithm reaches a strictly positive product using the minimum possible number of operations. Therefore, it is correct.

Complexity

For each test case, we scan the array once.

Time complexity: $O(n)$

Memory complexity: $O(1)$