PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
You’re given a binary string S representing a signal. S_i = 0 represents silence in the i-th second, while S_i = 1 represents a pulse.
Find the number of pulses that occurred after at least one silence.
EXPLANATION:
Suppose the first silence appears at time t.
Then, every pulse that appears after t is valid, while every pulse that appears before t is invalid.
So, it’s important for us to find the value of t.
This is simple: just iterate through S and check for the leftmost i such that S_i = 0; this becomes t.
Once t is known, the answer is the number of pulses after t.
This is again simple: iterate through S starting from index t+1, and then add 1 to the answer if S_i = 1.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
s = input()
ans, flag = 0, 0
for i in range(n):
if s[i] == '0': flag = 1
else: ans += flag
print(ans)