Minimum operations to make array elements zero

Array Math Bit Manipulation

60.4% acceptance

Feb 25, 2026

385

You are given a 2D array queries, where queries[i] is of the form [l, r]. Each queries[i] defines an array of integers nums consisting of elements ranging from l to r, both inclusive. In one operation, you can: Select two integers a and b from the array. Replace them with floor(a / 4) and floor(b / 4). Your task is to determine the minimum number of operations required to reduce all elements of the array to zero for each query. Return the sum of the results for all queries.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(queries: Vec<Vec<i32>>) -> i64 {
    // For query [l, r]: array = [l, l+1, ..., r]. 
    // Each op: pick 2 elements, divide both by 4 (floor).
    // Min ops to reduce all to 0.
    // Number of ops to reduce x to 0: ceil(log4(x+1)) = number of times to divide by 4 until 0.
    // Each op handles 2 elements simultaneously.
    // Total "steps" for each element: steps(x) = ceil(log_4(x+1)) = number of times dividing x by 4 until 0.
    // Actually steps(x) = floor(log_4(x)) + 1 for x > 0; 0 for x = 0.
    // But each op reduces two elements by one "step" each (they're independent after pairing).
    // Actually: in one op, we pick elements a and b and replace with floor(a/4), floor(b/4).
    // This does NOT mean a and b have to be at the same "level".
    // Min ops = ceil(sum of steps(x) for all x in [l,r] / 2).
    // Wait: each element needs steps(x) operations. Each op decrements the "step counter" of 2 elements.
    // Min ops = ceil(sum_steps / 2).
    // steps(x) for x in [l,r]: sum via prefix sums.
    // steps(x) = 0 if x==0, else floor(log4(x))+1 = number of "layers" of 4.
    // For x in [1, 3]: steps=1. [4,15]: steps=2. [16,63]: steps=3. etc.
    // Sum of steps in [l,r] = sum over k >= 1 of count(x in [l,r] with steps(x) >= k)
    //                        = sum over k >= 1 of count(x in [l,r] with x >= 4^(k-1))
    // For k >= 1: count = max(0, r - max(l-1, 4^(k-1)-1)) = max(0, min(r, ...) - max(l-1, 4^k_lo - 1))
    // Sum over queries using O(log(max)) per query.
    let mut total = 0i64;
    for q in &queries {
      let l = q[0] as i64; let r = q[1] as i64;
      // Sum steps(x) for x = l..=r
      let sum_steps_fn = |limit: i64| -> i64 {
        if limit <= 0 { return 0; }
        let mut sum = 0i64;
        let mut lo = 1i64; // start of current level (4^(k-1))
        loop {
          if lo > limit { break; }
          let cnt = (limit - lo + 1).max(0);
          sum += cnt;
          lo *= 4;
        }
        sum
      };
      let sum_r = sum_steps_fn(r);
      let sum_l = sum_steps_fn(l - 1);
      let sum_steps = sum_r - sum_l;
      total += (sum_steps + 1) / 2;
    }
    total
  }
}