Python3 Program for Products of ranges in an array
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).
Python3
# Python3 program to find # Product in range Queries in O(N) # Function to calculate Product # in the given range. def calculateProduct (A, L, R, P): # As our array is 0 based # and L and R are given as # 1 based index. L = L - 1 R = R - 1 ans = 1 for i in range (R + 1 ): ans = ans * A[i] ans = ans % P return ans # Driver code A = [ 1 , 2 , 3 , 4 , 5 , 6 ] P = 229 L = 2 R = 5 print (calculateProduct(A, L, R, P)) L = 1 R = 3 print (calculateProduct(A, L, R, P)) # This code is contributed # by "Abhishek Sharma 44" |
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.
Python3
# Python3 implementation of the # above approach # 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 def modInverse(a, m): m0, x0, x1 = m, 0 , 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 = a % m, t t = x0 x0 = x1 - q * x0 x1 = t # Make x1 positive if x1 < 0 : x1 + = m0 return x1 # calculating pre_product array def calculate_Pre_Product(A, N, P): pre_product[ 0 ] = A[ 0 ] for i in range ( 1 , N): pre_product[i] = pre_product[i - 1 ] * A[i] pre_product[i] = pre_product[i] % P # Calculating inverse_product # array. def calculate_inverse_product(A, N, P): inverse_product[ 0 ] = modInverse(pre_product[ 0 ], P) for i in range ( 1 , N): inverse_product[i] = modInverse(pre_product[i], P) # Function to calculate # Product in the given range. def 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 ans = 0 if L = = 0 : ans = pre_product[R] else : ans = pre_product[R] * inverse_product[L - 1 ] return ans # Driver Code if __name__ = = "__main__" : # Array A = [ 1 , 2 , 3 , 4 , 5 , 6 ] N = len (A) # Prime P P = 113 MAX = 100 pre_product = [ None ] * ( MAX ) inverse_product = [ None ] * ( MAX ) # Calculating PreProduct # and InverseProduct calculate_Pre_Product(A, N, P) calculate_inverse_product(A, N, P) # Range [L, R] in 1 base index L, R = 2 , 5 print (calculateProduct(A, L, R, P)) L, R = 1 , 3 print (calculateProduct(A, L, R, P)) # This code is contributed by Rituraj Jain |
Output :
7 6
Please refer complete article on Products of ranges in an array for more details!