Given an array A[] of size N. Solve Q queries. Find the product in the range [L, R] under modulo P ( P is Prime).
Examples:
Input : A[] = {1, 2, 3, 4, 5, 6}
L = 2, R = 5, P = 229
Output : 120
Input : A[] = {1, 2, 3, 4, 5, 6},
L = 2, R = 5, P = 113
Output : 7
Brute Force
For each of the queries, traverse each element in the range [L, R] and calculate the product under modulo P. This will answer each query in O(N).
Javascript
<script> // Product in range Queries in O(N) // Function to calculate // Product in the given range. function calculateProduct(A, L, R, P) { // As our array is 0 based // as and L and R are given // as 1 based index. L = L - 1; R = R - 1; let ans = 1; for (let i = L; i <= R; i++) { ans = ans * A[i]; ans = ans % P; } return ans; } let A = [ 1, 2, 3, 4, 5, 6 ]; let P = 229; let L = 2, R = 5; document.write(calculateProduct(A, L, R, P) + "</br>"); L = 1; R = 3; document.write(calculateProduct(A, L, R, P) + "</br>"); </script> |
Output :
120 6
Efficient Using Modular Multiplicative Inverse:
As P is prime, we can use Modular Multiplicative Inverse. Using dynamic programming, we can calculate a pre-product array under modulo P such that the value at index i contains the product in the range [0, i]. Similarly, we can calculate the pre-inverse product under modulo P. Now each query can be answered in O(1).
The inverse product array contains the inverse product in the range [0, i] at index i. So, for the query [L, R], the answer will be Product[R]*InverseProduct[L-1]
Note: We can not calculate the answer as Product[R]/Product[L-1] because the product is calculated under modulo P. If we do not calculate the product under modulo P there is always a possibility of overflow.
Javascript
<script> // Javascript program to find Product // in range Queries in O(1) let MAX = 100; let pre_product = new Array(MAX); let inverse_product = new Array(MAX); // Returns modulo inverse of // a with respect to m using // extended Euclid Algorithm // Assumption: a and m are // coprimes, i.e., gcd(a, m) = 1 function modInverse(a, m) { let m0 = m, t, q; let x0 = 0, x1 = 1; if (m == 1) return 0; while (a > 1) { // q is quotient q = parseInt(a / m, 10); t = m; // m is remainder now, process // same as Euclid's algo m = a % m; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } // Make x1 positive if (x1 < 0) x1 += m0; return x1; } // calculating pre_product array function calculate_Pre_Product(A, N, P) { pre_product[0] = A[0]; for (let i = 1; i < N; i++) { pre_product[i] = pre_product[i - 1] * A[i]; pre_product[i] = pre_product[i] % P; } } // Calculating inverse_product // array. function calculate_inverse_product(A, N, P) { inverse_product[0] = modInverse(pre_product[0], P); for (let i = 1; i < N; i++) inverse_product[i] = modInverse(pre_product[i], P); } // Function to calculate Product // in the given range. function calculateProduct(A, L, R, P) { // As our array is 0 based as // and L and R are given as 1 // based index. L = L - 1; R = R - 1; let ans; if (L == 0) ans = pre_product[R]; else ans = pre_product[R] * inverse_product[L - 1]; return ans; } // Array let A = [ 1, 2, 3, 4, 5, 6 ]; // Prime P let P = 113; // Calculating PreProduct and // InverseProduct calculate_Pre_Product(A, A.length, P); calculate_inverse_product(A, A.length, P); // Range [L, R] in 1 base index let L = 2, R = 5; document.write(calculateProduct(A, L, R, P) + "</br>"); L = 1; R = 3; document.write(calculateProduct(A, L, R, P)); </script> |
Output :
7 6
Please refer complete article on Products of ranges in an array for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
