aboutsummaryrefslogtreecommitdiff
path: root/range_product_queries_powers.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-04-08 10:09:32 -0600
committerJack Sangdahl <[email protected]>2025-04-08 10:09:32 -0600
commit66e44e00b92d3959ec640525055d652c3d3d7756 (patch)
tree0b78e8e5b361f1bf2ba0fafbc47aaaf34719dd63 /range_product_queries_powers.py
parent3fdd56c0adaccc960214af925cdc5c19bf3d187a (diff)
downloadleetcode-66e44e00b92d3959ec640525055d652c3d3d7756.tar.gz
leetcode-66e44e00b92d3959ec640525055d652c3d3d7756.zip
2438. range product queries of power
Diffstat (limited to 'range_product_queries_powers.py')
-rw-r--r--range_product_queries_powers.py41
1 files changed, 41 insertions, 0 deletions
diff --git a/range_product_queries_powers.py b/range_product_queries_powers.py
new file mode 100644
index 0000000..81b31f9
--- /dev/null
+++ b/range_product_queries_powers.py
@@ -0,0 +1,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]]))