3145. Find Products of Elements of Big Array Hard

1/**
2 * [3145] Find Products of Elements of Big Array
3 *
4 * The powerful array of a non-negative integer x is defined as the shortest sorted array of powers of two that sum up to x. The table below illustrates examples of how the powerful array is determined. It can be proven that the powerful array of x is unique.
5 * <table border="1">
6 * 	<tbody>
7 * 		<tr>
8 * 			<th>num</th>
9 * 			<th>Binary Representation</th>
10 * 			<th>powerful array</th>
11 * 		</tr>
12 * 		<tr>
13 * 			<td>1</td>
14 * 			<td>0000<u>1</u></td>
15 * 			<td>[1]</td>
16 * 		</tr>
17 * 		<tr>
18 * 			<td>8</td>
19 * 			<td>0<u>1</u>000</td>
20 * 			<td>[8]</td>
21 * 		</tr>
22 * 		<tr>
23 * 			<td>10</td>
24 * 			<td>0<u>1</u>0<u>1</u>0</td>
25 * 			<td>[2, 8]</td>
26 * 		</tr>
27 * 		<tr>
28 * 			<td>13</td>
29 * 			<td>0<u>11</u>0<u>1</u></td>
30 * 			<td>[1, 4, 8]</td>
31 * 		</tr>
32 * 		<tr>
33 * 			<td>23</td>
34 * 			<td><u>1</u>0<u>111</u></td>
35 * 			<td>[1, 2, 4, 16]</td>
36 * 		</tr>
37 * 	</tbody>
38 * </table>
39 * The array big_nums is created by concatenating the powerful arrays for every positive integer i in ascending order: 1, 2, 3, and so on. Thus, big_nums begins as [<u>1</u>, <u>2</u>, <u>1, 2</u>, <u>4</u>, <u>1, 4</u>, <u>2, 4</u>, <u>1, 2, 4</u>, <u>8</u>, ...].
40 * You are given a 2D integer matrix queries, where for queries[i] = [fromi, toi, modi] you should calculate (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi<!-- notionvc: a71131cc-7b52-4786-9a4b-660d6d864f89 -->.
41 * Return an integer array answer such that answer[i] is the answer to the i^th query.
42 *  
43 * <strong class="example">Example 1:
44 * <div class="example-block">
45 * Input: <span class="example-io">queries = [[1,3,7]]</span>
46 * Output: <span class="example-io">[4]</span>
47 * Explanation:
48 * There is one query.
49 * big_nums[1..3] = [2,1,2]. The product of them is 4. The result is 4 % 7 = 4.
50 * </div>
51 * <strong class="example">Example 2:
52 * <div class="example-block">
53 * Input: <span class="example-io">queries = [[2,5,3],[7,7,4]]</span>
54 * Output: <span class="example-io">[2,2]</span>
55 * Explanation:
56 * There are two queries.
57 * First query: big_nums[2..5] = [1,2,4,1]. The product of them is 8. The result is 8 % 3 = 2.
58 * Second query: big_nums[7] = 2. The result is 2 % 4 = 2.
59 * </div>
60 *  
61 * Constraints:
62 * 
63 * 	1 <= queries.length <= 500
64 * 	queries[i].length == 3
65 * 	0 <= queries[i][0] <= queries[i][1] <= 10^15
66 * 	1 <= queries[i][2] <= 10^5
67 * 
68 */
69pub struct Solution {}
70
71// problem: https://leetcode.com/problems/find-products-of-elements-of-big-array/
72// discuss: https://leetcode.com/problems/find-products-of-elements-of-big-array/discuss/?currentPage=1&orderBy=most_votes&query=
73
74// submission codes start here
75
76impl Solution {
77    pub fn find_products_of_elements(queries: Vec<Vec<i64>>) -> Vec<i32> {
78        vec![]
79    }
80}
81
82// submission codes end
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    #[test]
89    fn test_3145() {
90    }
91}
92