diff options
author | Jack Sangdahl <[email protected]> | 2025-04-08 10:09:32 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-04-08 10:09:32 -0600 |
commit | 66e44e00b92d3959ec640525055d652c3d3d7756 (patch) | |
tree | 0b78e8e5b361f1bf2ba0fafbc47aaaf34719dd63 | |
parent | 3fdd56c0adaccc960214af925cdc5c19bf3d187a (diff) | |
download | leetcode-66e44e00b92d3959ec640525055d652c3d3d7756.tar.gz leetcode-66e44e00b92d3959ec640525055d652c3d3d7756.zip |
2438. range product queries of power
-rw-r--r-- | range_product_queries_powers.c | 79 | ||||
-rw-r--r-- | range_product_queries_powers.py | 41 |
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]])) |