Minimum Operations to Reduce an Integer to 0

Medium
704.

Minimum Operations to Reduce an Integer to 0

Minimum Operations to Reduce an Integer to 0 is a medium coding problem on dynamic programming, greedy and bit manipulation, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var minOperationsToZero = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Reduce an Integer to 0 — Solution

Minimum Operations to Reduce an Integer to 0 solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Reduce an Integer to 0 is a medium coding problem on dynamic programming, greedy and bit manipulation, asked in Amazon, Google and Microsoft interviews.

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

Hints for Minimum Operations to Reduce an Integer to 0

  1. Hint 1

    Each operation clears or creates one bit, so think about the binary form of n.

  2. Hint 2

    A lone set bit costs one operation. A run of set bits is cheaper to clear by adding 1 to the run and then removing the carried bit.

  3. Hint 3

    Walking the bits from the bottom: if the low two bits are 11, add 1; if the low bit is 1, subtract 1; otherwise shift right.

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

  1. While n > 0: if n % 4 == 3, add 1 and count an operation — this collapses a run of ones.
  2. Else if n is odd, subtract 1 and count an operation.
  3. 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

Java

public static int minOperationsToZero(int n) {
    int ops = 0;
    long v = n;
    while (v > 0) {
        if (v % 4 == 3) { v += 1; ops++; }
        else if (v % 2 == 1) { v -= 1; ops++; }
        else v /= 2;
    }
    return ops;
}

C++

int minOperationsToZero(int n) {
    int ops = 0;
    long long v = n;
    while (v > 0) {
        if (v % 4 == 3) { v += 1; ops++; }
        else if (v % 2 == 1) { v -= 1; ops++; }
        else v /= 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Greedy Algorithms