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