aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--range_product_queries_powers.c79
-rw-r--r--range_product_queries_powers.py41
2 files changed, 120 insertions, 0 deletions
diff --git a/range_product_queries_powers.c b/range_product_queries_powers.c
new file mode 100644
index 0000000..fb70f41
--- /dev/null
+++ b/range_product_queries_powers.c
@@ -0,0 +1,79 @@
+// 2438. Range Product Queries of Powers
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+const int mod = 1e9 + 7;
+
+void get_products(int *powers, long long *seg, int root, int low, int high) {
+ if (low == high) {
+ seg[root] = powers[low];
+ return;
+ }
+ int i = (root << 1) + 1;
+ int mid = (low + high) >> 1;
+ get_products(powers, seg, i, low, mid);
+ get_products(powers, seg, i + 1, mid + 1, high);
+ seg[root] = (seg[i] * seg[i + 1]) % mod;
+}
+
+int range_query(long long *seg, int root, int low, int high, int left,
+ int right) {
+ if (high < left || low > right)
+ return 1;
+ if (low >= left && high <= right)
+ return seg[root];
+ int i = (root << 1) + 1;
+ int mid = (low + high) >> 1;
+ long p1 = range_query(seg, i, low, mid, left, right);
+ long p2 = range_query(seg, i + 1, mid + 1, high, left, right);
+ return (p1 * p2) % mod;
+}
+
+int *productQueries(int n, int **queries, int queriesSize, int *queriesColSize,
+ int *returnSize) {
+ int powers[33], ns = 0, mask = 1;
+ while (n > 0) {
+ if (n & mask) {
+ powers[ns++] = mask;
+ n &= ~mask;
+ }
+ mask <<= 1;
+ }
+ long long seg[150];
+ get_products(powers, seg, 0, 0, ns - 1);
+ int *ans = (int *)malloc(queriesSize * sizeof(int));
+ for (int i = 0; i < queriesSize; ++i)
+ ans[i] = range_query(seg, 0, 0, ns - 1, queries[i][0], queries[i][1]);
+ *returnSize = queriesSize;
+ return ans;
+}
+
+int main() {
+ int q1i[3][2] = {{0, 1}, {2, 2}, {0, 3}}, q2i[1][2] = {{0, 0}};
+ struct two_d_arr q1, q2;
+ two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
+ two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
+ int rs1, *pq1 = productQueries(15, q1.arr, q1.row_size, q1.col_size, &rs1);
+ int rs2, *pq2 = productQueries(2, q2.arr, q2.row_size, q2.col_size, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", pq1[i]); // expect: 2 4 6
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", pq2[i]); // expect: 2
+ printf("\n");
+ free(pq1);
+ free(pq2);
+ two_d_arr_free(&q1);
+ two_d_arr_free(&q2);
+}
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]]))