Find products of elements of big array

Array Binary Search Bit Manipulation

24.5% acceptance

Feb 24, 2026

The powerful array of a non-negative integer x is defined as the shortest sorted array of powers of two that sum up to x. The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so on. Thus, big_nums begins as [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...]. You are given a 2D integer matrix queries, where for queries[i] = [fromi, toi, modi] you should calculate (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi. Return an integer array answer such that answer[i] is the answer to the ith query.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_products_of_elements(queries: Vec<Vec<i64>>) -> Vec<i32> {
    // count_bits_upto(n): total elements in big_nums from integers 1..=n
    // = Sum_{i=1}^{n} popcount(i) = Sum_{j=0..50} count_in_1_to_n_with_bit_j
    fn count_bits_upto(n: i64) -> i64 {
      if n <= 0 {
        return 0;
      }
      let mut result = 0i64;
      for j in 0u32..50 {
        let cycle = 1i64 << (j + 1);
        let full = (n + 1) / cycle;
        let rem = (n + 1) % cycle;
        result += full * (1i64 << j);
        let over = rem - (1i64 << j);
        if over > 0 {
          result += over;
        }
      }
      result
    }

    // exp_sum_upto(n): sum of all bit-positions for all elements in big_nums from 1..=n
    // = Sum_{j=0..50} j * count_in_1_to_n_with_bit_j
    fn exp_sum_upto(n: i64) -> i128 {
      if n <= 0 {
        return 0;
      }
      let mut result = 0i128;
      for j in 0u32..50 {
        let cycle = 1i64 << (j + 1);
        let full = (n + 1) / cycle;
        let rem = (n + 1) % cycle;
        let cnt = full * (1i64 << j) + 0i64.max(rem - (1i64 << j));
        result += (j as i128) * (cnt as i128);
      }
      result
    }

    // find smallest n such that count_bits_upto(n) > pos (i.e., element at pos is in block n)
    fn find_n_for_pos(pos: i64) -> i64 {
      let mut lo = 1i64;
      let mut hi = 2i64;
      while count_bits_upto(hi) <= pos {
        hi *= 2;
      }
      while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if count_bits_upto(mid) <= pos {
          lo = mid + 1;
        } else {
          hi = mid;
        }
      }
      lo
    }

    // exp_prefix(pos): sum of bit-positions of big_nums[0], ..., big_nums[pos-1]
    fn exp_prefix(pos: i64) -> i128 {
      if pos <= 0 {
        return 0;
      }
      let n = find_n_for_pos(pos - 1);
      let base_count = count_bits_upto(n - 1);
      let mut total = exp_sum_upto(n - 1);
      let offset = (pos - 1) - base_count; // 0-based position within block n
      // Sum bit positions of the first (offset+1) set bits of n (LSB first)
      let mut val = n;
      let mut cnt = offset + 1;
      while cnt > 0 {
        total += val.trailing_zeros() as i128;
        val &= val - 1; // clear lowest set bit
        cnt -= 1;
      }
      total
    }

    fn mod_pow(mut base: i128, mut exp: i128, modulus: i64) -> i64 {
      if modulus == 1 {
        return 0;
      }
      let m = modulus as i128;
      let mut result = 1i128;
      base %= m;
      while exp > 0 {
        if exp & 1 == 1 {
          result = result * base % m;
        }
        base = base * base % m;
        exp >>= 1;
      }
      result as i64
    }

    queries
      .iter()
      .map(|q| {
        let from = q[0];
        let to = q[1];
        let modi = q[2];
        // Product of big_nums[from..=to] = 2^(sum of exponents in [from,to])
        let total_exp = exp_prefix(to + 1) - exp_prefix(from);
        mod_pow(2, total_exp, modi) as i32
      })
      .collect()
  }
}