MAKESUB - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N cells in a row, each painted either black or white.
You can paint a white cell black, but not the other way around.
How many cells do you have to paint to make all the black cells form a contiguous segment?

EXPLANATION:

If there are initially no black cells (so every cell is white), then nothing needs to be painted.

Otherwise, let the leftmost black cell be at index L, and the rightmost black cell be at index R.
Observe that no matter what, all cells from L to R need to end up black (either from being initially black, or we paint them black) - otherwise the black cells can’t be connected.

Further, it’s clearly useless to paint any cells to the left of L or to the right of R.

So, the solution is simply:

  • Find L, the leftmost black cell.
  • Find R, the rightmost black cell.
  • The answer is the number of white cells in the range [L, R].
    This can be computed by just iterating through the range and counting them; or alternately by noting that this count equals the length of the segment [L, R] minus the number of black cells.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    s = input()
    left, right = -1, -2
    for i in range(n):
        if s[i] == '1':
            right = i
            if left == -1: left = i    
    print(right - left + 1 - s.count('1'))