Range Product Queries of Powers Solution in Java

Quick Links

Problem Description

Welcome to the world of Range Product Queries of Powers! Imagine you’re at a party, and everyone is trying to figure out how many snacks they can eat without going overboard. You have a magical number n, which represents the total number of snacks available, and a series of queries asking for the product of snacks between two indices. Sounds simple, right? Well, it’s like trying to find the last slice of pizza at a party where everyone is eyeing it!

In this problem, you need to calculate the product of powers of 2 that correspond to the bits set in the binary representation of n. Each query gives you a range, and you need to return the product of the powers of 2 for that range, modulo 10⁹ + 7.

Code Solution


class Solution {
  public int[] productQueries(int n, int[][] queries) {
    final int kMod = 1_000_000_007;
    final int kMaxBit = 30;
    int[] ans = new int[queries.length];
    List powers = new ArrayList<>();

    for (int i = 0; i < kMaxBit; ++i)
      if ((n >> i & 1) == 1)
        powers.add(1 << i);

    for (int i = 0; i < queries.length; ++i) {
      final int left = queries[i][0];
      final int right = queries[i][1];
      long prod = 1;
      for (int j = left; j <= right; ++j) {
        prod *= powers.get(j);
        prod %= kMod;
      }
      ans[i] = (int) prod;
    }

    return ans;
  }
}

Approach

The approach taken in this solution is quite straightforward. First, we identify the powers of 2 that correspond to the bits set in the binary representation of n. We store these powers in a list. For each query, we calculate the product of the powers of 2 in the specified range and return the result modulo 10⁹ + 7.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(q · m), where q is the number of queries and m is the maximum range of indices in the queries.
Space Complexity	O(k), where k is the number of bits set in `n`.

Real-World Example

Imagine you’re at a buffet with a limited number of dishes (like the bits in n). Each dish represents a power of 2, and you can only eat from certain dishes based on your friends' requests (the queries). You need to calculate how many dishes you can eat from a specific range without going overboard. This problem is a fun way to simulate that scenario!