Smallest value of X satisfying the condition X % A [ i ] = B [ i ] for two given arrays | Java program for the above approach ; 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
import java . io . * ; import java . lang . * ; import java . util . * ; public class Main { static int inv ( 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 ; } static int findMinX ( int A [ ] , int B [ ] , int N ) { int prod = 1 ; for ( int i = 0 ; i < N ; i ++ ) prod *= A [ i ] ; int result = 0 ; for ( int i = 0 ; i < N ; i ++ ) { int pp = prod / A [ i ] ; result += B [ i ] * inv ( pp , A [ i ] ) * pp ; } return result % prod ; } static int product ( int a [ ] ) { int ans = 1 ; for ( int i = 0 ; i < a . length ; i ++ ) { ans *= a [ i ] ; } return ans ; } public static void findSmallestInteger ( int A [ ] , int B [ ] , int P ) { int Y = findMinX ( A , B , A . length ) ; int M = product ( A ) ; int K = ( int ) Math . ceil ( ( ( double ) P - ( double ) Y ) / ( double ) M ) ; int X = Y + K * M ; System . out . println ( X ) ; } public static void main ( String [ ] args ) { int A [ ] = { 3 , 4 , 5 } ; int B [ ] = { 2 , 3 , 1 } ; int P = 72 ; findSmallestInteger ( A , B , P ) ; } }