Flip the Switches

View as PDF

Submit solution

Points: 5
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Megumin is trying to deactivate a security system! The security system is composed of N different switches, and is only fully deactivated when all of the switches are off. Let's define flipping a switch as changing it from on to off, or vice versa. Megumin has thought of the ingenious idea of exploding the whole thing flipping the switches with her staff to avoid detection! However, given her position, she can only use her staff to flip a prefix of the switches (switches 1 to k, 1 \le k \le N) in one click. Can you help her figure out the minimum number of clicks needed to fully deactivate the system without using explosion?

Input Specification

The first line will contain an integer N (1 \le N \le 10^6).

The next line will contain a string of N characters 0 and 1, representing the states of the switches from 1 to N (0 is off, 1 is on).

Output Specification

Output the minimum number of clicks required to fully deactivate the system.

Sample Input


Sample Output


Explanation for Sample Output

Megumin can use her staff to flip the first 3 switches, changing the states to 0111.

Then she can flip all the switches, changing the states to 1000.

Finally, she can use her staff to flip the first switch, changing the states to 0000 and fully deactiviating the system.


There are no comments at the moment.