Smallest value of X satisfying the condition X % A[i] = B[i] for two given arrays

0 0 10 minutes read

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 Algorithm
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
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[]
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 condition
void 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 Code
int 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 approach
 
import 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 approach
import math
 
# Function to calculate modulo
# inverse of a w.r.t m using
# Extended Euclid Algorithm
def 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 X
def 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 condition
def 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 Code
if __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 approach
using 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 Algorithm
function 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 X
function 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 condition
function 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 Code
var A = [ 3, 4, 5 ];
var B = [ 2, 3, 1 ];
var n = A.length;
var P = 72;
findSmallestInteger(A, B, P,n);
 
</script>

Output:

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 zambiatek!