Products of ranges in an array | Java program to find Product in range Queries in O ( 1 ) ; 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 ; q is quotient ; m is remainder now , process same as Euclid 's algo ; Make x1 positive ; calculating pre_product array ; Cacluating inverse_product array . ; Function to calculate Product in the given range . ; As our array is 0 based as and L and R are given as 1 based index . ; Driver code ; Array ; Prime P ; Calculating PreProduct and InverseProduct ; Range [ L , R ] in 1 base index
class GFG { static int MAX = 100 ; int pre_product [ ] = new int [ MAX ] ; int inverse_product [ ] = new int [ MAX ] ; int modInverse ( int a , int m ) { int m0 = m , t , q ; int x0 = 0 , x1 = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { q = a / m ; t = m ; m = a % m ; a = t ; t = x0 ; x0 = x1 - q * x0 ; x1 = t ; } if ( x1 < 0 ) x1 += m0 ; return x1 ; } void 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 ; } } 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 ) ; } int calculateProduct ( int A [ ] , int L , int R , int P ) { 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 ; } public static void main ( String [ ] s ) { GFG d = new GFG ( ) ; int A [ ] = { 1 , 2 , 3 , 4 , 5 , 6 } ; int P = 113 ; d . calculate_Pre_Product ( A , A . length , P ) ; d . calculate_inverse_product ( A , A . length , P ) ; 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 ) ) ; } }