# 2438. Range Product Queries of Powers
"""
given a positive integer 'n', there exists a 0-indexed array called 'powers'
composed of the minimum number of powers of 2 that sum to 'n'. the array is
sorted in non-decreasing order, and there is only one way to form the array.
you are also given a 0-indexed 2d integer array 'queries' where 'queries[i] =
[left_i, right_i]'. each 'queries[i]' represents a query where you have to
find the product of all 'powers[j]' with 'left_i <= j <= right_i'. return an
array 'answers', equal in length to 'queries', where 'answers[i]' is the
answer to each i'th query. since the answer may be too large, each
'answers[i]' should be returned modulo 10e9+7.
"""
class Solution(object):
def productQueries(self, n, queries):
"""
:type n: int
:type queries: List[List[int]]
:rtype: List[int]
"""
mod, powers, i = 10**9 + 7, [], 0
while n > 0:
if n & 1:
powers.append(1 << i)
n >>= 1
i += 1
ans = []
for left, right in queries:
prod = 1
for i in range(left, right + 1):
prod = (prod * powers[i]) % mod
ans.append(prod)
return ans
if __name__ == "__main__":
obj = Solution()
print(obj.productQueries(n=15, queries=[[0, 1], [2, 2], [0, 3]]))
print(obj.productQueries(n=2, queries=[[0, 0]]))
