Products of ranges in an array | Javascript 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 . ; Array ; Prime P ; Calculating PreProduct and InverseProduct ; Range [ L , R ] in 1 base index
let MAX = 100 ; let pre_product = new Array ( MAX ) ; let inverse_product = new Array ( MAX ) ; function modInverse ( a , m ) { let m0 = m , t , q ; let x0 = 0 , x1 = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { q = parseInt ( a / m , 10 ) ; t = m ; m = a % m ; a = t ; t = x0 ; x0 = x1 - q * x0 ; x1 = t ; } if ( x1 < 0 ) x1 += m0 ; return x1 ; } 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 ; } } 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 calculateProduct ( A , L , R , P ) { 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 ; } let A = [ 1 , 2 , 3 , 4 , 5 , 6 ] ; let P = 113 ; calculate_Pre_Product ( A , A . length , P ) ; calculate_inverse_product ( A , A . length , P ) ; let L = 2 , R = 5 ; document . write ( calculateProduct ( A , L , R , P ) + " " ) ; L = 1 ; R = 3 ; document . write ( calculateProduct ( A , L , R , P ) ) ;