## Flip the Switches

View as PDF

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

Author:
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 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 to , ) 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 ().

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

#### Output Specification

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

#### Sample Input

4
1001

#### Sample Output

3

#### 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.