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.
- Difficulty: Medium
- Topics: Bit Manipulation, Enumeration, Brainteaser
- 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
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
Hint 1
After exactly
koperations,num1 - k·num2must equal a sum ofkpowers of two.Hint 2
A positive
xis a sum of exactlykpowers of two (repeats allowed) if and only ifpopcount(x) <= k <= x.Hint 3
Try
k = 1, 2, …, 60and 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
- For
kfrom 1 to 60, computex = num1 - k·num2in 64 bits. - If
x >= kand the number of 1-bits ofxis at mostk, returnk. - If no
kworks, 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·num2reaches 6·10^10 — computexin 64 bits (JavaScript numbers are exact here, but 32-bit bitwise operators are not).xmust be at leastk: each operation removes at least 1 fromx's power-of-two budget.- Do not stop at the first
kwithx < kwhennum2is negative — thenxgrows withk.
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 -1Java
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