We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Operations to Make the Integer Zero

Number: 2837

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two integers num1 and num2, you may perform operations where in each operation you choose an integer i (0 ≤ i ≤ 60) and subtract (2^i + num2) from num1. The goal is to make num1 equal to 0 in the minimum number of operations. If it is impossible, return -1.

Key Insights

  • Every operation subtracts a fixed offset (num2) in addition to a power‐of‐2. Hence after k operations, the total subtracted value is (sum of k chosen powers of 2) + k * num2.
  • Let m = num1 – k * num2. Then we must “pay” m using k powers of 2. Since each operation contributes one power–of–2 and we can choose the same power more than once, m must be expressible as (x0 * 2^0 + x1 * 2^1 + … + x60 * 2^60) with nonnegative integers x_i satisfying sum(x_i) = k.
  • A necessary (and sufficient) condition is: • m ≥ k (since each 2^i is at least 1) and • The number of 1’s in any representation (the “bit count”) of m can be “covered” by k operations, i.e. bit_count(m) ≤ k.
  • There is one further feasibility check: because the maximum power that can be subtracted in one operation is 2^60, the sum from all operations is at most k * 2^60. Therefore, we must also have m ≤ k * 2^60.
  • By testing increasing values of k (the number of operations), the minimum valid k (with m = num1 – k * num2 nonnegative, m in [k, k*2^60], and bit_count(m) ≤ k) gives the answer. If no such k exists within the search range then the answer is –1.

Space and Time Complexity

Time Complexity: O(K · log(m)) where K is the number of operations we try (in practice K is very small under the given constraints) and log(m) comes from computing the bit count. Space Complexity: O(1)

Solution

The idea is to try possible values for k (the number of operations) starting from 1. For each k, compute m = num1 – k * num2. We must have: • m must be nonnegative (otherwise we overshot). • Since each operation contributes at least 1 (using the smallest power 2^0 = 1), we must have m ≥ k. • It is only possible to “pay” m using k operations if the minimum number of summands needed (which is the bit count of m, allowing repeated use of the same power) is at most k. • Also, m cannot exceed k*2^60 because each operation can subtract at most 2^60. If these conditions hold, then k is a valid candidate. We return the minimum such k. Otherwise, if no k in our search range works, we return –1.

Key data structures: simple integer arithmetic and use of a loop. The algorithm uses a greedy search on k and takes advantage of bit manipulation (counting the number of ones in the binary representation) to check if m can be “assembled” from k powers of two.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line‐by‐line comments.

# Python solution

def minimumOperations(num1: int, num2: int) -> int:
    # For some cases, we can quickly decide the answer:
    # For example, if num2 == 0 then each operation subtracts a power of two.
    # The answer is simply the number of ones in the binary representation of num1.
    if num2 == 0:
        return bin(num1).count("1")
    
    # For num2 > 0, note that m = num1 - k*num2 must be nonnegative.
    # Thus, k must be at most num1 // num2 (if num2 > 0).
    # For num2 < 0, m increases with k so we choose an upper bound for k.
    max_k = 10**6 if num2 < 0 else num1 // num2 + 1

    TWO_POWER_60 = 1 << 60  # maximum power-of-2 allowed in one operation
    
    # Iterate for possible number of operations k
    for k in range(1, max_k + 1):
        m = num1 - k * num2  # total number that should be paid by powers of 2.
        if m < k: 
            # m is too small to be represented as sum of k positive powers (each at least 1)
            continue
        if m > k * TWO_POWER_60:
            # m is too large to be achieved even if each operation gave the maximum 2^60
            continue
        # The minimal number of summands required is the total count of ones in the binary
        # representation of m (since we can use the same power-of-2 more than once, the bit count
        # is a lower bound on the number of summands needed).
        if bin(m).count("1") <= k <= m:
            return k
    return -1

# Example test
print(minimumOperations(3, -2))  # Expected output: 3
print(minimumOperations(5, 7))   # Expected output: -1
← Back to All Questions