Minimum Operations to Make the Integer Zero

Minimum Operations to Make the Integer Zero - Problem

You are given two integers num1 and num2.

In one operation, you can choose integer i in the range [0, 60] and subtract 2ⁱ + 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.

Input & Output

Example 1 — Basic Case

$ Input: num1 = 11, num2 = 1

› Output: 3

💡 Note: We need 3 operations: 11 - (2³ + 1) - (2⁰ + 1) - (2⁰ + 1) = 11 - 9 - 2 - 2 = 0. So we subtract (8+1), (1+1), (1+1) in 3 operations.

Example 2 — Impossible Case

$ Input: num1 = 1, num2 = -7

› Output: -1

💡 Note: Each operation adds to num1 (since we subtract negative num2), making it impossible to reach 0 from positive num1.

Example 3 — Single Operation

$ Input: num1 = 3, num2 = 2

› Output: 1

💡 Note: One operation: 3 - (2⁰ + 2) = 3 - 3 = 0. We subtract (1+2) in 1 operation.

Constraints

1 ≤ num1 ≤ 10⁹
-10⁹ ≤ num2 ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

num1=11, num2=1 - need to make num1 zero

Operations

Each operation subtracts 2^i + num2 for some i ∈ [0,60]

Solution

Find minimum operations needed, or -1 if impossible

Key Takeaway

🎯 Key Insight: Transform the problem into finding k such that (num1 - k*num2) can be expressed as sum of exactly k powers of 2

Asked in

M Microsoft 15 G Google 12

The key insight is that each operation subtracts 2ⁱ + num2, so after k operations we need k*num2 + sum of k powers of 2 = num1. For a target sum to be expressible as k powers of 2, we need bitCount ≤ k ≤ target. Best approach is optimized enumeration with mathematical bounds. Time: O(log(num1)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Enumeration	O(k)	O(1)	Try all possible numbers of operations from 1 to a reasonable upper bound
Mathematical Bounds Optimization	O(log(num1))	O(1)	Use tighter mathematical bounds to reduce the search space

Brute Force Enumeration — Algorithm Steps

Try k operations from 1 to 50
For each k, check if (num1 - k*num2) can be expressed as sum of k powers of 2
Return the minimum valid k, or -1 if none found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try k=1

Check if num1 - 1*num2 can be one power of 2

Try k=2

Check if num1 - 2*num2 can be sum of two powers of 2

Continue

Keep trying until we find valid k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countBits(long long n) {
    int count = 0;
    while (n) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

int solution(int num1, int num2) {
    for (int k = 1; k <= 50; k++) {
        long long target = (long long)num1 - (long long)k * num2;
        if (target <= 0) continue;
        
        if (target < k) continue;
        
        int bitCount = countBits(target);
        if (bitCount <= k && k <= target) {
            return k;
        }
    }
    return -1;
}

int main() {
    int num1, num2;
    scanf("%d", &num1);
    scanf("%d", &num2);
    printf("%d\n", solution(num1, num2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

We try up to 50 operations, each check is O(1)

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

423 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler