Minimum operations to reduce an integer to 0

Dynamic Programming Greedy Bit Manipulation

61.1% acceptance

Feb 25, 2026

619

200

You are given a positive integer n, you can do the following operation any number of times: Add or subtract a power of 2 from n. Return the minimum number of operations to make n equal to 0. A number x is power of 2 if x == 2i where i >= 0.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(n: i32) -> i32 {
    let mut n = n as u32;
    let mut ops = 0;
    while n != 0 {
      ops += 1;
      let lsb = n & n.wrapping_neg(); // lowest set bit
      if n & (lsb << 1) != 0 {
        // Two consecutive set bits: round up (add lsb to propagate carry)
        n += lsb;
      } else {
        // Isolated set bit: subtract it
        n -= lsb;
      }
    }
    ops
  }
}