Leetcode: 2438. Range Product Queries of Powers

Problem Statement

Understand the problem

Given an integer \(n\) and queries \(q=(l,r)\), return for each query the product of \(p[l:r]\) where \(p\) are the powers of \(2\) in non-decreasing order that compose \(n\).

Devise a plan

Compute all powers of 2 in \(n\) and for each query use Brute Force to compute the answer by multiplying all required powers of 2.

Carry out the plan

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7
        p = []
        c = 1
        while c <= n:
            if n & c != 0:
                p.append(c)
            c *= 2

        ans = []
        for start, end in queries:
            cur = p[start] % MOD
            for j in range(start + 1, end + 1):
                cur = (cur * p[j]) % MOD
            ans.append(cur)
        return ans