Minimum Operations to Reduce an Integer to 0 — Medium Problem & Solution

In one operation you may add or subtract any power of 2 to n. Return the minimum number of operations that turns n into 0.

Difficulty: Medium
Topics: Dynamic Programming, Greedy, Bit Manipulation
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

In one operation you may add or subtract any power of 2 to n.

Return the minimum number of operations that turns n into 0.

Example 1

Input: n = 39
Output: 3
Explanation: 39 + 1 = 40, 40 - 8 = 32, 32 - 32 = 0.

Example 2

Input: n = 54
Output: 3
Explanation: 54 + 2 = 56, 56 + 8 = 64, 64 - 64 = 0.

Example 3

Input: n = 4
Output: 1
Explanation: 4 is already a power of two.

Constraints

1 <= n <= 100000000

How to solve Minimum Operations to Reduce an Integer to 0

Process the bits from least significant upward. A single trailing 1 is best removed by subtracting; two or more consecutive trailing 1s are best cleared by adding 1, which carries them away and leaves one higher bit to deal with.

Approach

While n > 0: if n % 4 == 3, add 1 and count an operation — this collapses a run of ones.
Else if n is odd, subtract 1 and count an operation.
Else divide by 2, moving to the next bit at no cost.

Why it works

n % 4 == 3 means the two lowest bits are both 1, so the run has length at least 2 and adding 1 clears them all at the cost of one carry — strictly better than subtracting 1 for each. A lone trailing 1 (n % 4 == 1) has no run to collapse, so subtracting is optimal. Shifting an even number costs nothing because the low bit is already 0.

Complexity

Time — O(log n)
Space — O(1)

Pitfalls

Counting the set bits of n gives the wrong answer for runs: 7 costs 2 operations, not 3.
Always adding on an odd number loops forever on n = 1, which must be handled by subtracting.
Adding 1 can push n above the original magnitude — that is expected and is why the carry chain terminates.

Reference solution

Python

def minOperationsToZero(n: int) -> int:
    ops = 0
    while n > 0:
        if n % 4 == 3:
            n += 1
            ops += 1
        elif n % 2 == 1:
            n -= 1
            ops += 1
        else:
            n //= 2
    return ops

JavaScript

var minOperationsToZero = function(n) {
    var ops = 0;
    while (n > 0) {
        if (n % 4 === 3) { n += 1; ops++; }
        else if (n % 2 === 1) { n -= 1; ops++; }
        else n = n / 2;
    }
    return ops;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 195 dynamic programming problems · the whole catalogue