Minimum operations to make the integer zero

Bit Manipulation Brainteaser Enumeration

58.2% acceptance

Feb 25, 2026

768

375

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn make_the_integer_zero(num1: i32, num2: i32) -> i32 {
    // After k operations: need sum of k powers-of-2 = num1 - k*num2 = val
    // This is possible iff val > 0, popcount(val) <= k, and val >= k
    for k in 1i64..=64 {
      let val = num1 as i64 - k * num2 as i64;
      if val > 0 && (val as u64).count_ones() as i64 <= k && val >= k {
        return k as i32;
      }
    }
    -1
  }
}