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).
Java
// Product in range Queries in O(N)import java.io.*;class GFG{ // Function to calculate // Product in the given range. static int calculateProduct(int []A, int L, int R, int P) { // As our array is 0 based as // and L and R are given as 1 // based index. L = L - 1; R = R - 1; int ans = 1; for (int i = L; i <= R; i++) { ans = ans * A[i]; ans = ans % P; } return ans; } // Driver code static public void main (String[] args) { int []A = { 1, 2, 3, 4, 5, 6 }; int P = 229; int L = 2, R = 5; System.out.println( calculateProduct(A, L, R, P)); L = 1; R = 3; System.out.println( calculateProduct(A, L, R, P)); }}// This code is contributed by vt_m. |
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.
Java
// Java program to find Product// in range Queries in O(1)class GFG{static int MAX = 100;int pre_product[] = new int[MAX];int inverse_product[] = new int[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) = 1int modInverse(int a, int m){ int m0 = m, t, q; int x0 = 0, x1 = 1; if (m == 1) return 0; while (a > 1) { // q is quotient q = a / m; 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 arrayvoid calculate_Pre_Product(int A[], int N, int P){ pre_product[0] = A[0]; for (int 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.void calculate_inverse_product(int A[], int N, int P){ inverse_product[0] = modInverse(pre_product[0], P); for (int i = 1; i < N; i++) inverse_product[i] = modInverse(pre_product[i], P);}// Function to calculate Product// in the given range.int calculateProduct(int A[], int L, int R, int P){ // As our array is 0 based as and // L and R are given as 1 based index. L = L - 1; R = R - 1; int ans; if (L == 0) ans = pre_product[R]; else ans = pre_product[R] * inverse_product[L - 1]; return ans;}// Driver codepublic static void main(String[] s){ GFG d = new GFG(); // Array int A[] = { 1, 2, 3, 4, 5, 6 }; // Prime P int P = 113; // Calculating PreProduct and // InverseProduct d.calculate_Pre_Product(A, A.length, P); d.calculate_inverse_product(A, A.length, P); // Range [L, R] in 1 base index int L = 2, R = 5; System.out.println(d.calculateProduct(A, L, R, P)); L = 1; R = 3; System.out.println(d.calculateProduct(A, L, R, P)); }}// This code is contributed by Prerna Saini |
Output :
7 6
Please refer complete article on Products of ranges in an array for more details!
