Description

There are many coins placed in a row. Heads-up is represented by $1$, and tails-up is represented by $0$.

Starting from the first coin in the row, in each operation you must flip the first several coins simultaneously, i.e., choose some $k \ge 1$ and flip the first $k$ coins. What is the minimum number of such operations needed to make all coins heads-up?

Input Format

A string consisting of $0$ and $1$, representing the initial state of the coins.

Output Format

An integer, the minimum number of flips required.

10

2

Hint

Sample Explanation

For example, for input 10:

• The $1$-st flip: flip the first coin to tails; the string becomes 00.
• The $2$-nd flip: flip the first and second coins together to heads; the string becomes 11. Flipping is complete, so the output is $2$.

Constraints

Let $n$ be the total number of coins.

• For $20\%$ of the testdata, $1\le n\leq10$.
• For $50\%$ of the testdata, $1\le n\leq10^4$.
• For $100\%$ of the testdata, $1\le n\leq10^6$.

Translated by ChatGPT 5