 # ZEROSTRING - Editorial

Author: notsoloud
Testers: iceknight1093, yash_daga
Editorialist: iceknight1093

TBD

None

# PROBLEM:

You have a binary string S of length N. You can either delete one character from S or flip every character of S.
Find the minimum number of moves to obtain a string consisting of all zeros.

# EXPLANATION:

First, notice that the order in which operations are performed doesn’t really matter.
So, let’s perform all flips before all deletions.

Now, note that it’s never optimal to perform a flip operation more than once — flipping an even number of times is equivalent to not flipping at all; while flipping an odd number of times is equivalent to flipping once.

So, we flip either zero times or one time.

• If we flip zero times, our only option is to delete every 1 from the string.
• If we flip one time, we must delete every 1 from the flipped string. The number of these equals the number of zeros in the original string.

So, suppose S has c_0 zeros and c_1 ones. The answer is then \min(c_1, 1+c_0).

# TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

# CODE:

Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
s = input()
zc, oc = s.count('0'), s.count('1')
print(min(oc, 1+zc))