aboutsummaryrefslogtreecommitdiff
path: root/range_product_queries_powers.py
blob: 81b31f93b1f21371974965eeafc3cc162819e1d1 (plain)
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 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]]))