#2571

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Operations to Reduce an Integer to 0

Compute the minimum number of operations to reduce a positive integer to zero using additions or subtractions of powers of two efficiently.

dynamic programming greedy bit manipulation

Problem Statement

Given a positive integer n, you may repeatedly perform an operation where you add or subtract any power of two (2^i for i >= 0). Each operation counts as one step.

Determine the minimum number of operations required to reduce n to exactly zero, leveraging strategic choices of powers of two for optimal reduction.

Examples

Example 1

Input: n = 39

Output: 3

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

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

Solution Approach

Dynamic Programming with State Transitions

Define dp[x] as the minimum operations to reach x. Iterate through reachable numbers by adding or subtracting powers of two, updating dp states to ensure the minimum count propagates. This mirrors the state transition DP pattern.

Greedy Bit Manipulation Heuristic

Observe the binary representation of n. Consider flipping the least significant bit toward zero or adjusting the next higher power when beneficial. This reduces unnecessary operations while still aligning with the DP states.

Combine DP and Bit Decisions

Integrate greedy bit decisions into the DP framework by only expanding states that represent optimal bit manipulations. This prevents exploring redundant paths and speeds up finding the minimum number of operations.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the chosen approach; naive BFS can be O(n log n) due to powers of two exploration, while optimized DP with bit manipulation reduces redundant states. Space complexity is dominated by the number of states tracked in DP.

What Interviewers Usually Probe

They may hint at using binary representation to simplify operations.
Expect discussion of state transition or dynamic programming strategy.
Watch for opportunities to combine greedy bit-level optimization with DP.

Common Pitfalls or Variants

Common pitfalls

Attempting only subtraction without considering additions of powers of two.
Not limiting state expansion leads to excessive memory usage.
Ignoring the benefit of flipping higher-order bits for faster reduction.

Follow-up variants

Minimize operations when only subtraction of powers of two is allowed.
Find maximum integer reachable within k operations of powers of two.
Count distinct sequences of operations that reduce n to zero.

FAQ

What is the best approach for Minimum Operations to Reduce an Integer to 0?

A state transition dynamic programming approach combined with bit manipulation is optimal, ensuring minimal operations by simulating all reachable states efficiently.

Can I solve this using only greedy strategies?

Greedy bit flipping helps, but without DP, it may miss sequences that reduce n in fewer operations.

How does bit manipulation help reduce operations?

Examining binary representation identifies which powers of two to add or subtract, preventing unnecessary moves and aligning with optimal DP states.

What are common mistakes when implementing this problem?

Ignoring addition operations, over-expanding states, or not considering higher-order bit flips can all lead to suboptimal solutions.

Does this problem have a strict time constraint?

Yes, naive exploration of all possible powers without DP or bit optimization can be too slow for larger n.

terminal

Solution

Solution 1: Greedy + Bitwise Operation

We convert the integer $n$ to binary, starting from the lowest bit:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minOperations(self, n: int) -> int:
        ans = cnt = 0
        while n:
            if n & 1:
                cnt += 1
            elif cnt:
                ans += 1
                cnt = 0 if cnt == 1 else 1
            n >>= 1
        if cnt == 1:
            ans += 1
        elif cnt > 1:
            ans += 2
        return ans

Continue Practicing

#2708 maximum strength of a group #3068 find the maximum sum of node values #2572 count the number of square free subsets