SOLVE
LATER
Let \(\textrm{pop}(n)\) is number ones n have in binary. For example, \(\textrm{pop}(11) = \textrm{pop}(1011_2) = 3.\)
For integer d, define
\(f(d) = \min_{n \geqslant 0} \textrm{pop}(n \oplus (n + d)).\)
Here \(\oplus\) denotes binary XOR.
You are given d in binary, find \(f(d)\).
Input Format:
Single line contains binary representation of d without leading zeroes.
Output Format:
One integer in decimal numeral system -- \(f(d).\)
Constraints:
\( 1 \leqslant d < 2 ^ {200,000}.\)
50 points
\( 1 \leqslant d < 2 ^ {40}.\)
Here \(d = 11_2 = 3.\)