Minimum Operations to Make the Integer Zero

Medium
1322.

Minimum Operations to Make the Integer Zero

Minimum Operations to Make the Integer Zero is a medium coding problem on bit manipulation, enumeration and brainteaser, asked in Amazon, Google and Microsoft interviews.

You are given two integers num1 and num2. In one operation you pick an integer i with 0 <= i <= 60 and subtract 2^i + num2 from num1.

Return the minimum number of operations needed to make num1 exactly 0, or -1 if it is impossible.

Example 1

Input
num1 = 10, num2 = 1
Output
2
Explanation
Subtract 2^2 + 1 = 5 twice: 10 → 5 → 0.

Example 2

Input
num1 = 6, num2 = 10
Output
-1
Explanation
Every operation subtracts at least 11, so 6 can never land exactly on 0.

Example 3

Input
num1 = 7, num2 = 0
Output
3
Explanation
7 = 4 + 2 + 1 needs three powers of two.

Constraints

  • 1 <= num1 <= 10^9
  • -10^9 <= num2 <= 10^9
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} num1
 * @param {number} num2
 * @return {number}
 */
var makeTheIntegerZero = function(num1, num2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Operations to Make the Integer Zero — Solution

Minimum Operations to Make the Integer Zero solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Operations to Make the Integer Zero is a medium coding problem on bit manipulation, enumeration and brainteaser, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given two integers num1 and num2. In one operation you pick an integer i with 0 <= i <= 60 and subtract 2^i + num2 from num1.

Return the minimum number of operations needed to make num1 exactly 0, or -1 if it is impossible.

Example 1

Input: num1 = 10, num2 = 1
Output: 2
Explanation: Subtract 2^2 + 1 = 5 twice: 10 → 5 → 0.

Example 2

Input: num1 = 6, num2 = 10
Output: -1
Explanation: Every operation subtracts at least 11, so 6 can never land exactly on 0.

Example 3

Input: num1 = 7, num2 = 0
Output: 3
Explanation: 7 = 4 + 2 + 1 needs three powers of two.

Constraints

  • 1 <= num1 <= 10^9
  • -10^9 <= num2 <= 10^9

Hints for Minimum Operations to Make the Integer Zero

  1. Hint 1

    After exactly k operations, num1 - k·num2 must equal a sum of k powers of two.

  2. Hint 2

    A positive x is a sum of exactly k powers of two (repeats allowed) if and only if popcount(x) <= k <= x.

  3. Hint 3

    Try k = 1, 2, …, 60 and return the first that satisfies the condition — the values involved need 64-bit integers.

How to solve Minimum Operations to Make the Integer Zero

Fix the number of operations k. The num2 parts add up to k·num2 no matter which powers are chosen, so the question becomes whether x = num1 - k·num2 is a sum of exactly k powers of two — which holds exactly when popcount(x) <= k <= x.

Approach

  1. For k from 1 to 60, compute x = num1 - k·num2 in 64 bits.
  2. If x >= k and the number of 1-bits of x is at most k, return k.
  3. If no k works, return -1.

Why it works

The fewest powers of two that sum to x is popcount(x) (its binary digits), and the most is x (all ones). Every count in between is reachable, because splitting a power 2^j with j >= 1 into two copies of 2^(j-1) raises the count by exactly one. So k operations suffice exactly when popcount(x) <= k <= x. For k >= 36 any x >= k qualifies (x <= 6.1·10^10 < 2^36 has at most 36 one-bits), and the powers stay within 2^60, so if an answer exists it appears well before 60.

Complexity

  • Time — O(60 · 64)
  • Space — O(1)

Pitfalls

  • k·num2 reaches 6·10^10 — compute x in 64 bits (JavaScript numbers are exact here, but 32-bit bitwise operators are not).
  • x must be at least k: each operation removes at least 1 from x's power-of-two budget.
  • Do not stop at the first k with x < k when num2 is negative — then x grows with k.

Reference solution

Python

def makeTheIntegerZero(num1: int, num2: int) -> int:
    for k in range(1, 61):
        x = num1 - k * num2
        if x >= k and bin(x).count("1") <= k:
            return k
    return -1

Java

public static int makeTheIntegerZero(int num1, int num2) {
    for (int k = 1; k <= 60; k++) {
        long x = (long) num1 - (long) k * num2;
        if (x >= k && Long.bitCount(x) <= k) return k;
    }
    return -1;
}

C++

int makeTheIntegerZero(int num1, int num2) {
    for (int k = 1; k <= 60; k++) {
        long long x = (long long) num1 - (long long) k * num2;
        if (x >= k && __builtin_popcountll(x) <= k) return k;
    }
    return -1;
}

JavaScript

var makeTheIntegerZero = function(num1, num2) {
    for (var k = 1; k <= 60; k++) {
        var x = num1 - k * num2;
        if (x < k) continue;
        var ones = 0, t = x;
        while (t > 0) {
            ones += t % 2;
            t = Math.floor(t / 2);
        }
        if (ones <= k) return k;
    }
    return -1;
};

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

All 146 bit manipulation problems · the whole catalogue

Learn the technique: Bit Manipulation