Good Colouring

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

Joe recently flunked the CCC (Canadian Computing Competition) and has decided to switch from programming to colouring instead.

In order for a chance to qualify for the prestigious Canadian Colouring Olympiad (CCO), he needs to be able to be able to colour a "good" stripe pattern, which consists of a row of colours that alternate between colour 0 and colour 1. Examples of good stripe patterns include 010101 and 101 but not 100.

After realizing that he just painted a bad stripe pattern, Joe plans to use his magic paintbrush, which, in a single stroke can change the colour of a single position on his pattern from either colour 0 to colour 1 or vice versa. Given Joe's current stripe pattern as a string of 0s and 1s, determine the minimum number of magic brush strokes Joe needs to make his stripe pattern "good".

Input Specification

The first line contains an integer N (1 \le N \le 2 \times 10^5), the length of his pattern.

The second line contains a string of N characters, each consisting of either 0 or 1.

Subtask 1 [5%]

The original pattern will only consist of colour 0.

Subtask 2 [10%]

1 \le N \le 18

Subtask 3 [85%]

No additional constraints

Output Specification

Output one integer: the minimum number of magic brush strokes needed to turn is pattern into a "good" stripe pattern.

Sample Input


Sample Output


Explanation for Sample Case

Joe can use his magic paintbrush to turn the last stripe to colour 0, making the pattern 01010, which is a "good" stripe pattern, taking a total of 1 magic brush stroke.


There are no comments at the moment.