MOG
Spanish
|
English

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

The 2021 ICPC Caribbean Finals (Qualifier) - Warmup

Ended

C - Coloring tiles

Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (details)

At Fito's garden, $N$ tiles are arranged in a row. The initial color of each tile is represented by a string $S$ of length $N$. The $i$-th tile from the left is painted black if the $i$-th character of $S$ is $0$ and painted white if that character is $1$.

Fito wants to repaint some of the tiles black or white so that any two adjacent tiles have different colors. What is the minimum amount of tiles that he need to repaint in order to satisfy this condition?

Input

The first line of input contains the string $S$ ($1 \leq |S| \leq 10^5$). Each character of $S$ is either $0$ or $1$.

Output

The minimum number of tiles that Fito needs to repaint in order to satisfy the condition.

Sample test(s)

Input
000
Output
1
Input
10010010
Output
3
Input
0
Output
0

Hints

In the first example, Fito could repaint the second tile and the sequence would be $010$ (any two adjacent tiles have different colors). Therefore the minimum amount of tiles to repaint is $1$ since at least one has to be repainted because the original sequence does not satisfy the condition.