Limits 1s, 512 MB

Solving a problem during a programming contest is always a moment of happiness. During the CUET CSE fest programming contest, team XsX’s solved status is denoted by a binary string SS of size NN where for all (1iN)(1 \leq i \leq N), Si=1S_i = 1 means team XX has already solved this problem and Si=0S_i = 0 means they haven’t solved this yet. Recall that a binary string is a non-empty sequence of characters where each character is either 0 or 1.

After a few hours of the contest, judge pc suddenly started acting weirdly. When a team solves a problem, the next problem automatically gets accepted. In other words, if XX solves problem i i (i1N)(i\leq 1 \leq N) that is SiS_i becomes 11 then Si+1S_{i+1} also becomes 11 if (i+1N)(i + 1 \leq N).

Team XX found this fault and wants to make the best use of it. Your task is to find the minimum number of submissions team XX needs to make to solve all the problems. Here you can assume that if team XX makes a submission then it gets accepted.


The first line contains the value of NN (1N105)(1\leq N \leq 10^5)— the length of the binary string.

The second line contains a binary string SS and for all (1iN)(1 \leq i \leq N), SiS_i is either 00 or 11.


Print a single integer — minimum number of submissions team XX needs to make to solve all the problems.


  • First, team XX solves the first problem that is XX selects i=1i = 1 and the string becomes 11001.

  • Then, team XX solves the third problem that is XXselects i=3i = 3 and the string becomes 11111.



Login to submit.


95% Solution Ratio
KnightshadeEarliest, Dec '22
jahid_hridoyFastest, 0.0s
Srejon_KhanLightest, 4.9 MB
Marzuq01Shortest, 159B
Toph uses cookies. By continuing you agree to our Cookie Policy.