Given a positive integer n, you can add or subtract any power of 2 in one operation. Return the minimum number of operations to reduce n to 0.

Examples

Example 1:

Input: n = 39
Output: 3

39 = 100111₂
  39 + 1 = 40 (101000₂)     op 1: +2⁰
  40 - 8 = 32 (100000₂)     op 2: -2³
  32 - 32 = 0               op 3: -2⁵

Example 2:

Input: n = 54
Output: 3

54 = 110110₂
  54 + 2 = 56 (111000₂)     op 1: +2¹
  56 + 8 = 64 (1000000₂)    op 2: +2³
  64 - 64 = 0               op 3: -2⁶

Constraints

  • 1 <= n <= 10^5

Thinking Process

Binary Perspective

Every number is already a sum of powers of 2 (its binary representation). Each 1 bit could be removed by subtracting that power – that’s the naive approach, costing popcount(n) operations.

But we can do better by adding a power of 2 to create carries that collapse consecutive 1s.

When to Add vs Subtract

n = 7 = 111₂

Naive (subtract each bit): 4 + 2 + 1 → 3 ops
Smart: 7 + 1 = 8 (1000₂), then 8 - 8 = 0 → 2 ops

Adding 1 to a block of consecutive 1s collapses them all into a single 1 at a higher position.

The Greedy Rule

Scan from LSB to MSB:

  • Bit is 0 – shift right, nothing to do
  • Bit is 1:
    • If the next bit is also 1 (i.e., n & 3 == 3) – add 1 (carry forward to collapse the block)
    • Otherwise (isolated 1) – subtract 1 (cheaper to just remove it)

Each add/subtract counts as one operation. Shifting doesn’t count (we’re just moving to the next bit position).

Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Queue BFS (this problem) O(n) O(n) Shortest path in unweighted graphs
Multi-source BFS O(n) O(n) Start from all sources simultaneously
0-1 BFS / deque O(n) O(n) Weights 0 or 1
Level-order BFS O(n) O(w) Process by depth/layer

Solution

class Solution {
public:
    int minOperations(int n) {
        int ops = 0;
        while (n > 0) {
            if ((n & 1) == 0) {
                n >>= 1;
            } else if (n == 1) {
                return ops + 1;
            } else if ((n & 3) == 3) {
                n += 1;
                ops++;
            } else {
                n -= 1;
                ops++;
            }
        }
        return ops;
    }
};

Solution Explanation

Approach: Queue BFS (this problem)

Key idea: ### Binary Perspective

How the code works:

  • Bit is 0 – shift right, nothing to do
  • Bit is 1:
  • If the next bit is also 1 (i.e., n & 3 == 3) – add 1 (carry forward to collapse the block)
  • Otherwise (isolated 1) – subtract 1 (cheaper to just remove it)

Walkthrough — input n = 39, expected output 3:

  1. Initialize variables from the problem setup.
  2. Apply the main loop / recursion until the condition is met.
  3. Confirm the result matches the expected output.

    Comparison

Aspect Greedy (Bit Manipulation) BFS
Time O(log n) O(n log n)
Space O(1) O(n)
Correctness proof Requires greedy argument Guaranteed (shortest path)
Interview value Shows deep bit intuition Shows BFS modeling skill
Best for Production / follow-up optimization Proving correctness / verification

BFS is useful as a verification tool: run it on small inputs to confirm the greedy produces optimal results. In interviews, mentioning BFS as a brute-force baseline before presenting the greedy shows strong problem-solving structure.

Why the Greedy is Optimal

Consider a block of k consecutive 1s:

Strategy Operations
Subtract each bit individually k
Add 1 to collapse, then subtract the resulting bit 2

For k ge 3, adding is strictly better. For k = 2 (like 11₂ = 3), both cost 2 operations:

  • Add: 3 + 1 = 4, 4 - 4 = 0 (2 ops)
  • Subtract: 3 - 1 = 2, 2 - 2 = 0 (2 ops)

The greedy chooses to add for k >= 2, which is safe since it never costs more.

Common Mistakes

  • Treating n = 1 separately: After all shifts, n == 1 is the base case (isolated single bit). Forgetting this causes infinite loops.
  • Using n & 1 == 1 instead of n & 3 == 3: The decision depends on whether the next bit is also set, not just the current bit
  • Counting shifts as operations: Shifting is just moving to the next bit position, not an actual add/subtract operation
  • BFS without bounds: Without capping the search space, BFS explodes in memory

Key Takeaways

  • Think in binary when the problem involves powers of 2
  • Consecutive 1s can be collapsed by adding 1 – this is the core greedy insight
  • Check n & 3 == 3 (two lowest bits both set) to decide add vs subtract
  • BFS gives a provably optimal baseline; greedy gives O(log n) performance
  • The pattern “add to create carry, then subtract” appears in many bit manipulation problems

References

Template Reference