Smallest value of X satisfying the condition X % A [ i ] = B [ i ] for two given arrays | Function to calculate modulo inverse of a w . r . t m using Extended Euclid Algorithm ; Base Case ; Perform extended euclid algorithm ; q is quotient ; m is remainder now , process same as euclid 's algorithm ; If x1 is negative ; Make x1 positive ; Function to implement Chinese Remainder Theorem to find X ; Stores the product of array elements ; Traverse the array ; Update product ; Initialize the result ; Apply the above formula ; Function to calculate the product of all elements of the array a [ ] ; Stores product of all array elements ; Traverse the array ; Return the product ; Function to find the value of X that satisfies the given condition ; Stores the required smallest value using Chinese Remainder Theorem ; Stores the product of all array elements ; The equation is Y + K * M >= P Therefore , calculate K = ceil ( ( P - Y ) / M ) ; So , X = Y + K * M ; Print the resultant value of X ; Driver Code
function inv ( a , m ) { var m0 = m , t , q ; var x0 = 0 , x1 = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { q = parseInt ( a / m ) ; t = m ; m = a % m ; a = t ; t = x0 ; x0 = x1 - q * x0 ; x1 = t ; } if ( x1 < 0 ) x1 += m0 ; return x1 ; } function findMinX ( A , B , N ) { var prod = 1 ; for ( var i = 0 ; i < N ; i ++ ) prod *= A [ i ] ; var result = 0 ; for ( var i = 0 ; i < N ; i ++ ) { var pp = parseInt ( prod / A [ i ] ) ; result += B [ i ] * inv ( pp , A [ i ] ) * pp ; } return result % prod ; } function product ( a , n ) { var ans = 1 ; for ( var i = 0 ; i < n ; i ++ ) { ans *= a [ i ] ; } return ans ; } function findSmallestInteger ( A , B , P , n ) { var Y = findMinX ( A , B , n ) ; var M = product ( A , n ) ; var K = Math . ceil ( ( P - Y ) / M ) ; var X = Y + K * M ; document . write ( X ) ; } var A = [ 3 , 4 , 5 ] ; var B = [ 2 , 3 , 1 ] ; var n = A . length ; var P = 72 ; findSmallestInteger ( A , B , P , n ) ;