ZEROSTRING - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: notsoloud
Testers: iceknight1093, yash_daga
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

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))