Minimum Operations to Reduce an Integer to 0

You receive a positive integer n. Each move lets you add or subtract a value that is a power of two.

Determine the smallest number of moves needed to turn n into 0.

To retain the exact original bound of n < 2^60 in this setting, the function receives n as a decimal string.

Examples

Example 1:

Input: n = "10"

Output: 2

Explanation:

Subtract 2 to obtain 8, and then subtract 8 to arrive at 0.

Example 2:

Input: n = "26"

Output: 3

Explanation:

An optimal sequence is 26 -> 24 -> 32 -> 0.

Constraints

• n is a valid decimal representation of an integer
• 1 <= n < 2^60