Given a positive integer n, you may repeatedly perform the following operation any number of times.

In one operation, choose a nonnegative integer i and either add $2^i$ to n or subtract $2^i$ from n.

Return the minimum number of operations required to make n equal to $0$.

Constraints:

• $1 \leq$ n $\leq 10^5$

Input: n = 1-int
Output: 1-int
Explanation: Subtracting 2^0 = 1 takes 1 → 0 in one operation.

Input: n = 2-int
Output: 1-int
Explanation: Subtracting 2^1 = 2 takes 2 → 0 in one operation.

Input: n = 3-int
Output: 2-int
Explanation: One optimal sequence is subtracting 2^0 = 1 (3 → 2), then subtracting 2^1 = 2 (2 → 0), for a total of 2 operations. It cannot be done in 1 operation since 3 is not a power of two.

Input: n = 7-int
Output: 2-int
Explanation: Using an add to reach a power of two, adding 2^0 = 1 (7 → 8) and then subtracting 2^3 = 8 (8 → 0) takes 2 operations, which is better than subtracting powers of two repeatedly.

Input: n = 10-int
Output: 2-int
Explanation: 10 is not a power of two, but it’s close: subtracting 2^1 = 2 (10 → 8) and then 2^3 = 8 (8 → 0) takes 2 operations.

Input: n = 15-int
Output: 2-int
Explanation: Jumping up to the next power of two, adding 2^0 = 1 (15 → 16) and then subtracting 2^4 = 16 (16 → 0) takes 2 operations.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.