Skip to main content
Talentd

Minimum Operations to Make the Integer Zero - Solution & Explanation

MediumBit ManipulationBrainteaser12 min readAsked at: Amazon, Meta, Google +1
Practice this problem

Problem Statement

You are given two integers num1 and num2.

In one operation, you can choose integer i in the range [0, 60] and subtract 2i + num2 from num1.

Return the integer denoting the minimum number of operations needed to make num1 equal to 0.

If it is impossible to make num1 equal to 0, return -1.

 

Example 1:

Input: num1 = 3, num2 = -2
Output: 3
Explanation: We can make 3 equal to 0 with the following operations:
- We choose i = 2 and substract 22 + (-2) from 3, 3 - (4 + (-2)) = 1.
- We choose i = 2 and substract 22 + (-2) from 1, 1 - (4 + (-2)) = -1.
- We choose i = 0 and substract 20 + (-2) from -1, (-1) - (1 + (-2)) = 0.
It can be proven, that 3 is the minimum number of operations that we need to perform.

Example 2:

Input: num1 = 5, num2 = 7
Output: -1
Explanation: It can be proven, that it is impossible to make 5 equal to 0 with the given operation.

 

Constraints:

  • 1 <= num1 <= 109
  • -109 <= num2 <= 109

Approach Overview

Problem Overview: You start with two integers num1 and num2. In one operation you subtract (2^i + num2) from num1 for any non‑negative i. The goal is to reach exactly zero using the minimum number of operations.

Approach 1: Greedy Subtraction with Powers of 2 (O(60) time, O(1) space)

The key observation is that after performing k operations, the total value removed from the powers of two is x = num1 - k * num2. That means you must express x as the sum of exactly k powers of two. Using bit manipulation, this becomes a constraint on the binary representation of x. The number of set bits (popcount(x)) must be ≤ k because each set bit already represents one power of two, and larger powers can be split into smaller ones if more operations are needed.

You iterate over possible operation counts k (typically up to 60 because 2^60 exceeds the input bounds). For each k, compute x = num1 - k * num2. A valid solution exists if x ≥ k and popcount(x) ≤ k. The first k satisfying these conditions is the minimum number of operations. This greedy check works because any integer can be decomposed into powers of two using its binary form. The approach is extremely fast and relies heavily on properties of binary representation.

Approach 2: Dynamic Programming (DP) for Minimization (O(K * B) time, O(K) space)

A more explicit strategy models the process with dynamic programming. Treat each operation as selecting a power 2^i and subtracting num2 along with it. The DP tracks the minimum operations required to form different sums of powers of two while accounting for the cumulative subtraction of num2. Each state represents how many operations have been used and the achievable remainder value.

You iterate over possible powers of two and update states similarly to a knapsack transition. While this approach demonstrates the structure of the problem, the state space grows quickly because powers can repeat and the target value changes with every operation. In practice, DP is slower and more complex than the greedy insight derived from binary decomposition.

Recommended for interviews: The greedy check using popcount and binary constraints is the expected solution. It shows strong understanding of bit manipulation and mathematical reasoning. Mentioning a DP formulation can demonstrate problem exploration, but the constant‑time greedy iteration is what interviewers usually look for.

Approach 1: Approach 1: Greedy Subtraction with Powers of 2

This approach involves using a greedy method to subtract the largest possible power of 2 plus num2 from num1. At each step, we try to maximize the decrease in num1, aiming to reach exactly zero. If it becomes impossible to subtract without going below zero or exceeding the potential operations limit, we return -1.

The function iteratively subtracts the largest valid (2^i + num2) from num1. It counts the operations until num1 becomes zero. If num1 becomes negative and no valid i can be found, it returns -1.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(1) due to loop limits.
Space Complexity: O(1), only a few variables are used.

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming (DP) for Minimization

This approach leverages dynamic programming to store intermediate results of subproblems, reducing redundant calculations. We systematically explore the impact of subtracting each (2^i + num2) on num1, storing the minimum steps required to reach zero. This method is effective but requires more memory management.

This DP solution initializes a DP array where each index represents the minimum operations needed for that particular num1 value. Each valid operation updates the DP based on historical values.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(num1 * 61), for each num1 value, checks up to 61 possibilities for i.
Space Complexity: O(num1), required to store DP results for each subproblem.

Try this approach in the editor →

Approach 3: Enumeration

If we operate k times, then the problem essentially becomes: determining whether num1 - k times num2 can be split into the sum of k 2^is.

Let's assume x = num1 - k times num2. Next, we discuss in categories:

  • If x < 0, then x cannot be split into the sum of k 2^is, because 2^i > 0, which obviously has no solution;
  • If the number of 1s in the binary representation of x is greater than k, there is also no solution in this case;
  • Otherwise, for the current k, there must exist a splitting scheme.

Therefore, we start enumerating k from 1. Once we find a k that meets the condition, we can directly return the answer.

The time complexity is O(log x), and the space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy Subtraction with Powers of 2

Time Complexity: O(1) due to loop limits.
Space Complexity: O(1), only a few variables are used.

Approach 2: Dynamic Programming (DP) for Minimization

Time Complexity: O(num1 * 61), for each num1 value, checks up to 61 possibilities for i.
Space Complexity: O(num1), required to store DP results for each subproblem.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Subtraction with Powers of 2O(60)O(1)Best general solution using bit manipulation and binary popcount checks
Dynamic Programming for MinimizationO(K * B)O(K)Useful for conceptual understanding or when modeling the process explicitly

Video Solution

2749. Minimum Operations to Make the Integer Zero | Leetcode Daily - Python • Leetcode Daily • 3,314 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make the Integer Zero easy or hard?
The problem is rated Medium on LeetCode. The implementation is short, but the key insight—transforming the operations into constraints on the binary representation of num1 - k * num2—makes it a brainteaser that requires bit manipulation reasoning.
Minimum Operations to Make the Integer Zero Python/Java solution
Python and Java implementations both follow the same idea: iterate k from 1 to around 60, compute x = num1 - k * num2, and verify the constraints x ≥ k and bitCount(x) ≤ k. Python typically uses bin(x).count('1') while Java uses Integer.bitCount or Long.bitCount.
How to solve Minimum Operations to Make the Integer Zero in O(n)?
The problem can actually be solved faster than O(n). Iterate over possible operation counts k and compute x = num1 - k * num2. If x is non‑negative, popcount(x) ≤ k, and x ≥ k, then k operations can construct the value using powers of two. The first valid k is the answer.
What is the best approach for Minimum Operations to Make the Integer Zero?
The optimal approach iterates over the number of operations k and checks whether num1 - k * num2 can be represented as a sum of k powers of two. Using bit manipulation, the condition becomes popcount(x) ≤ k and x ≥ k where x = num1 - k * num2. This greedy check runs in constant time because k only needs to be tested up to about 60.
Is Minimum Operations to Make the Integer Zero asked at Google/Amazon/Meta?
Problems involving binary decomposition and bit manipulation frequently appear in interviews at companies like Google, Amazon, and Meta. This question tests reasoning about binary representation and greedy constraints, which are common themes in system‑level algorithm interviews.
What data structure is used in Minimum Operations to Make the Integer Zero?
The main technique is bit manipulation rather than a complex data structure. The algorithm relies on checking the number of set bits (popcount) in the binary representation of an integer and performing simple arithmetic operations.
What is the time complexity of Minimum Operations to Make the Integer Zero?
The optimal greedy solution runs in O(60) time and O(1) space. The algorithm only checks at most 60 possible operation counts because larger values exceed the limits of 64‑bit integers. Each iteration performs constant‑time arithmetic and a popcount operation.

Ready to solve this problem?

Practice Minimum Operations to Make the Integer Zero with our built-in code editor and test cases.

Practice on FleetCode
Previous

Broken Calculator

Next

Minimum Operations to Reduce X to Zero