Given two arrays A[] and B[], both consisting of N positive integers, an integer P and the elements of the array A[] are pairwise co-prime, the task is to find the smallest integer X which is at least P and X % A[i] is equal to B[i] for all i over the range of indices [0, N – 1].
Examples:
Input: A[] = {3, 4, 5}, B[] = {2, 3, 1}, P = 72
Output: 131
Explanation:
Consider the following operations for the value of X as 131.
- X % A[0] = 131 % 3 = 2 (= B[0])
- X % A[1] = 131 % 4 = 3 (= B[1])
- X % A[2] = 131 % 5 = 1 (= B[2])
Therefore, 131 is the smallest integer which is at least P( = 72).
Input: A[] = {5, 7}, B[] = {1, 3}, P = 0
Output: 31
Approach: The idea to solve the given problem is to use the Chinese Remainder Theorem. Follow the steps below to solve the given problem:
- Calculate the LCM of the array A[], which is equal to the product of all elements present in the array A[], say M, since all the elements are co-prime.
- Using Chinese Remainder Theorem, find the required smallest positive integer Y. Therefore, the value of X is given by (Y + K * M) for some integer K, that satisfies X % A[i] = B[i] for all i over the range of indices [0, N – 1].
- The value of K can be found from the equation Y + K * M >= P, which equates to K >= (P – Y)/M.
- Therefore, the required smallest possible integer X is (Y + K * M).
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include<bits/stdc++.h>using namespace std;// Function to calculate modulo// inverse of a w.r.t m using// Extended Euclid Algorithmint inv(int a, int m){ int m0 = m, t, q; int x0 = 0, x1 = 1; // Base Case if (m == 1) return 0; // Perform extended // euclid algorithm while (a > 1) { // q is quotient q = a / m; t = m; // m is remainder now, // process same as // euclid's algorithm m = a % m; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } // If x1 is negative if (x1 < 0) // Make x1 positive x1 += m0; return x1;}// Function to implement Chinese// Remainder Theorem to find Xint findMinX(int A[], int B[], int N){ // Stores the product // of array elements int prod = 1; // Traverse the array for(int i = 0; i < N; i++) // Update product prod *= A[i]; // Initialize the result int result = 0; // Apply the above formula for(int i = 0; i < N; i++) { int pp = prod / A[i]; result += B[i] * inv(pp, A[i]) * pp; } return result % prod;}// Function to calculate the product// of all elements of the array a[]int product(int a[], int n){ // Stores product of // all array elements int ans = 1; // Traverse the array for(int i = 0; i < n; i++) { ans *= a[i]; } // Return the product return ans;}// Function to find the value of X// that satisfies the given conditionvoid findSmallestInteger(int A[], int B[], int P, int n){ // Stores the required smallest value // using Chinese Remainder Theorem int Y = findMinX(A, B, n); // Stores the product // of all array elements int M = product(A,n); // The equation is Y + K*M >= P // Therefore, calculate K = ceil((P-Y)/M) int K = ceil(((double)P - (double)Y) / (double)M); // So, X = Y + K*M int X = Y + K * M; // Print the resultant value of X cout << X;}// Driver Codeint main(){ int A[] = { 3, 4, 5 }; int B[] = { 2, 3, 1 }; int n = sizeof(A) / sizeof(A[0]); int P = 72; findSmallestInteger(A, B, P,n);}// This code is contributed by SURENDRA_GANGWAR |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;public class Main { // Function to calculate modulo // inverse of a w.r.t m using // Extended Euclid Algorithm static int inv(int a, int m) { int m0 = m, t, q; int x0 = 0, x1 = 1; // Base Case if (m == 1) return 0; // Perform extended // euclid algorithm while (a > 1) { // q is quotient q = a / m; t = m; // m is remainder now, // process same as // euclid's algorithm m = a % m; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } // If x1 is negative if (x1 < 0) // Make x1 positive x1 += m0; return x1; } // Function to implement Chinese // Remainder Theorem to find X static int findMinX(int A[], int B[], int N) { // Stores the product // of array elements int prod = 1; // Traverse the array for (int i = 0; i < N; i++) // Update product prod *= A[i]; // Initialize the result int result = 0; // Apply the above formula for (int i = 0; i < N; i++) { int pp = prod / A[i]; result += B[i] * inv(pp, A[i]) * pp; } return result % prod; } // Function to calculate the product // of all elements of the array a[] static int product(int a[]) { // Stores product of // all array elements int ans = 1; // Traverse the array for (int i = 0; i < a.length; i++) { ans *= a[i]; } // Return the product return ans; } // Function to find the value of X // that satisfies the given condition public static void findSmallestInteger(int A[], int B[], int P) { // Stores the required smallest value // using Chinese Remainder Theorem int Y = findMinX(A, B, A.length); // Stores the product // of all array elements int M = product(A); // The equation is Y + K*M >= P // Therefore, calculate K = ceil((P-Y)/M) int K = (int)Math.ceil(((double)P - (double)Y) / (double)M); // So, X = Y + K*M int X = Y + K * M; // Print the resultant value of X System.out.println(X); } // Driver Code public static void main(String[] args) { int A[] = { 3, 4, 5 }; int B[] = { 2, 3, 1 }; int P = 72; findSmallestInteger(A, B, P); }} |
Python3
# Python3 program for the above approachimport math# Function to calculate modulo# inverse of a w.r.t m using# Extended Euclid Algorithmdef inv(a, m): m0 = m x0 = 0 x1 = 1 # Base Case if (m == 1): return 0 # Perform extended # euclid algorithm while (a > 1): # q is quotient q = a // m t = m # m is remainder now, # process same as # euclid's algorithm m = a % m a = t t = x0 x0 = x1 - q * x0 x1 = t # If x1 is negative if (x1 < 0): # Make x1 positive x1 += m0 return x1# Function to implement Chinese# Remainder Theorem to find Xdef findMinX(A, B, N): # Stores the product # of array elements prod = 1 # Traverse the array for i in range(N): # Update product prod *= A[i] # Initialize the result result = 0 # Apply the above formula for i in range(N): pp = prod // A[i] result += B[i] * inv(pp, A[i]) * pp return result % prod# Function to calculate the product# of all elements of the array a[]def product(a, n): # Stores product of # all array elements ans = 1 # Traverse the array for i in range(n): ans *= a[i] # Return the product return ans# Function to find the value of X# that satisfies the given conditiondef findSmallestInteger(A, B, P, n): # Stores the required smallest value # using Chinese Remainder Theorem Y = findMinX(A, B, n) # Stores the product # of all array elements M = product(A, n) # The equation is Y + K*M >= P # Therefore, calculate K = ceil((P-Y)/M) K = math.ceil((P - Y) / M) # So, X = Y + K*M X = Y + K * M # Print the resultant value of X print(X)# Driver Codeif __name__ == "__main__" : A = [ 3, 4, 5 ] B = [ 2, 3, 1 ] n = len(A) P = 72 findSmallestInteger(A, B, P, n)# This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;public class GFG { // Function to calculate modulo // inverse of a w.r.t m using // Extended Euclid Algorithm static int inv(int a, int m) { int m0 = m, t, q; int x0 = 0, x1 = 1; // Base Case if (m == 1) return 0; // Perform extended // euclid algorithm while (a > 1) { // q is quotient q = a / m; t = m; // m is remainder now, // process same as // euclid's algorithm m = a % m; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } // If x1 is negative if (x1 < 0) // Make x1 positive x1 += m0; return x1; } // Function to implement Chinese // Remainder Theorem to find X static int findMinX(int[] A, int[] B, int N) { // Stores the product // of array elements int prod = 1; // Traverse the array for (int i = 0; i < N; i++) // Update product prod *= A[i]; // Initialize the result int result = 0; // Apply the above formula for (int i = 0; i < N; i++) { int pp = prod / A[i]; result += B[i] * inv(pp, A[i]) * pp; } return result % prod; } // Function to calculate the product // of all elements of the array a[] static int product(int[] a) { // Stores product of // all array elements int ans = 1; // Traverse the array for (int i = 0; i < a.Length; i++) { ans *= a[i]; } // Return the product return ans; } // Function to find the value of X // that satisfies the given condition public static void findSmallestInteger(int[] A, int[] B, int P) { // Stores the required smallest value // using Chinese Remainder Theorem int Y = findMinX(A, B, A.Length); // Stores the product // of all array elements int M = product(A); // The equation is Y + K*M >= P // Therefore, calculate K = ceil((P-Y)/M) int K = (int)Math.Ceiling(((double)P - (double)Y) / (double)M); // So, X = Y + K*M int X = Y + K * M; // Print the resultant value of X Console.WriteLine(X); } // Driver Code public static void Main(string[] args) { int[] A = { 3, 4, 5 }; int[] B = { 2, 3, 1 }; int P = 72; findSmallestInteger(A, B, P); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to calculate modulo// inverse of a w.r.t m using// Extended Euclid Algorithmfunction inv(a, m){ var m0 = m, t, q; var x0 = 0, x1 = 1; // Base Case if (m == 1) return 0; // Perform extended // euclid algorithm while (a > 1) { // q is quotient q = parseInt(a / m); t = m; // m is remainder now, // process same as // euclid's algorithm m = a % m; a = t; t = x0; x0 = x1 - q * x0; x1 = t; } // If x1 is negative if (x1 < 0) // Make x1 positive x1 += m0; return x1;}// Function to implement Chinese// Remainder Theorem to find Xfunction findMinX(A, B, N){ // Stores the product // of array elements var prod = 1; // Traverse the array for(var i = 0; i < N; i++) // Update product prod *= A[i]; // Initialize the result var result = 0; // Apply the above formula 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 to calculate the product// of all elements of the array a[]function product(a, n){ // Stores product of // all array elements var ans = 1; // Traverse the array for(var i = 0; i < n; i++) { ans *= a[i]; } // Return the product return ans;}// Function to find the value of X// that satisfies the given conditionfunction findSmallestInteger(A, B, P, n){ // Stores the required smallest value // using Chinese Remainder Theorem var Y = findMinX(A, B, n); // Stores the product // of all array elements var M = product(A,n); // The equation is Y + K*M >= P // Therefore, calculate K = ceil((P-Y)/M) var K = Math.ceil((P - Y) / M); // So, X = Y + K*M var X = Y + K * M; // Print the resultant value of X document.write( X);}// Driver Codevar A = [ 3, 4, 5 ];var B = [ 2, 3, 1 ];var n = A.length;var P = 72;findSmallestInteger(A, B, P,n);</script> |
Output:
131
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
