Skip to content

2438. Range Product Queries of Powers 👍

  • Time: $O(q)$
  • Space: $O(q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  vector<int> productQueries(int n, vector<vector<int>>& queries) {
    constexpr int kMod = 1'000'000'007;
    constexpr int kMaxBit = 30;
    vector<int> ans;
    vector<int> powers;

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

    for (const vector<int>& query : queries) {
      const int left = query[0];
      const int right = query[1];
      long prod = 1;
      for (int i = left; i <= right; ++i) {
        prod *= powers[i];
        prod %= kMod;
      }
      ans.push_back(prod);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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<Integer> 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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def productQueries(self, n: int, queries: list[list[int]]) -> list[int]:
    kMod = 1_000_000_007
    kMaxBit = 30
    ans = []
    powers = [1 << i for i in range(kMaxBit) if n >> i & 1]

    for left, right in queries:
      prod = 1
      for i in range(left, right + 1):
        prod *= powers[i]
        prod %= kMod
      ans.append(prod)

    return ans