Minimal Popcount
Tag(s):

## Easy-Medium, Mathamatics, Mathematics, Mathematics, Simple-math

Problem
Editorial
Analytics

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}.$

SAMPLE INPUT
11

SAMPLE OUTPUT
2

Explanation

Here $d = 11_2 = 3.$

Time Limit: 5,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

March Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > Graphs
• Data Structures > Advanced Data Structures