Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation

• # Complement to 0 - advanced

We can reduce any number to 0 by repeatedly applying a complement operation to it in its binary form:
5 = 101 → 10 → 1 → 0 ⇒ 3 complement operations.
This time you’re asked to calculate the number of operations required to get to 0 for really large bit-strings.

#### Input

The input contains a single line representing the bit-string `s` (1 ≤ |s| ≤ ).

#### Output

The output should contain a single integer - the number of complement operations we need to perform to turn `s` into 0.

#### Examples

 Input Output 111111000111110011100 6

#### Explanation

111111000111110011100 → 111000001100011 → 111110011100 → 1100011 → 11100 → 11 → 0

#### Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB