2571

2571. Minimum Operations to Reduce an Integer to 0 (Medium)

You are given a positive integer n, you can do the following operation any number of times:

• Add or subtract a power of 2 from n.

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

A number x is power of 2 if x == 2i where i >= 0.

 

Example 1:

Input: n = 39
Output: 3
Explanation: We can do the following operations:
- Add 20 = 1 to n, so now n = 40.
- Subtract 23 = 8 from n, so now n = 32.
- Subtract 25 = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.

Example 2:

Input: n = 54
Output: 3
Explanation: We can do the following operations:
- Add 21 = 2 to n, so now n = 56.
- Add 23 = 8 to n, so now n = 64.
- Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.

 

Constraints:

• 1 <= n <= 105

Companies: Nvidia

Related Topics:
Dynamic Programming, Greedy, Bit Manipulation

Similar Questions:

• Plus One (Easy)

Solution 1. Greedy

// OJ: https://leetcode.com/problems/minimum-operations-to-reduce-an-integer-to-0
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    int minOperations(int n) {
        int ans = 0, one = 0;
        while (n) {
            int zero = 0;
            while (n & 1) n >>= 1, ++one;
            while (n && (n & 1) == 0) n >>= 1, ++zero;
            if (one == 1) ++ans, one = 0; // a single 1 -> remove it directly
            else if (one) { // For multiple 1s, we add at the rightmost 1. For example, 00111 -> 01000
                if (zero == 1) ++ans, one = 1; // if there is only a single leading 0, this new 1 is merged with the next batch of ones.
                else ans += 2, one = 0; // if there are multiple leading 0s, we remove this new 1
            }
        }
        return ans;
    }
};