13) Chinese Remainder Theorem
Given a system of simultaneous congruences, the Chinese Remainder Theorem provides a unique solution modulo the product of the moduli if the moduli are pairwise coprime.
Formula:
Below is the code snippet for Chinese Remainder Theorem:
// A C++ program to demonstrate working of Chinese remainder
// Theorem
#include <bits/stdc++.h>
using namespace std;
// k is size of num[] and rem[]. Returns the smallest
// number x such that:
// x % num[0] = rem[0],
// x % num[1] = rem[1],
// ..................
// x % num[k-2] = rem[k-1]
// Assumption: Numbers in num[] are pairwise coprime
// (gcd for every pair is 1)
int findMinX(int num[], int rem[], int k)
{
int x = 1; // Initialize result
// As per the Chinese remainder theorem,
// this loop will always break.
while (true) {
// Check if remainder of x % num[j] is
// rem[j] or not (for all j from 0 to k-1)
int j;
for (j = 0; j < k; j++)
if (x % num[j] != rem[j])
break;
// If all remainders matched, we found x
if (j == k)
return x;
// Else try next number
x++;
}
return x;
}
import java.util.Arrays;
public class ChineseRemainderTheorem {
// k is size of num[] and rem[]. Returns the smallest
// number x such that:
// x % num[0] = rem[0],
// x % num[1] = rem[1],
// ..................
// x % num[k-2] = rem[k-1]
// Assumption: Numbers in num[] are pairwise coprime
// (gcd for every pair is 1)
public static int findMinX(int num[], int rem[], int k)
{
int x = 1; // Initialize result
// As per the Chinese remainder theorem,
// this loop will always break.
while (true) {
// Check if remainder of x % num[j] is
// rem[j] or not (for all j from 0 to k-1)
int j;
for (j = 0; j < k; j++)
if (x % num[j] != rem[j])
break;
// If all remainders matched, we found x
if (j == k)
return x;
// Else try next number
x++;
}
}
public static void main(String args[])
{
int num[] = { 3, 4, 5 }; // Num array
int rem[] = { 2, 3, 1 }; // Rem array
int k = num.length;
System.out.println(
"The smallest number that is divisible by");
System.out.println(
"the given remainders and numbers is "
+ findMinX(num, rem, k));
}
}
// this code is contributed by monu.
# A Python program to demonstrate working of Chinese remainder
# Theorem
# k is size of num[] and rem[]. Returns the smallest
# number x such that:
# x % num[0] = rem[0],
# x % num[1] = rem[1],
# ..................
# x % num[k-2] = rem[k-1]
# Assumption: Numbers in num[] are pairwise coprime
# (gcd for every pair is 1)
def findMinX(num, rem, k):
x = 1 # Initialize result
# As per the Chinese remainder theorem,
# this loop will always break.
while True:
# Check if remainder of x % num[j] is
# rem[j] or not (for all j from 0 to k-1)
j = 0
while j < k:
if x % num[j] != rem[j]:
break
j += 1
# If all remainders matched, we found x
if j == k:
return x
# Else try next number
x += 1
return x
// Function to find the smallest number x such that:
// x % num[0] = rem[0],
// x % num[1] = rem[1],
// ..................
// x % num[k-2] = rem[k-1]
// Assumption: Numbers in num[] are pairwise coprime
// (gcd for every pair is 1)
function findMinX(num, rem) {
let x = 1; // Initialize result
// As per the Chinese remainder theorem,
// this loop will always break.
while (true) {
// Check if remainder of x % num[j] is
// rem[j] or not (for all j from 0 to k-1)
let j;
for (j = 0; j < num.length; j++) {
if (x % num[j] !== rem[j]) {
break;
}
}
// If all remainders matched, we found x
if (j === num.length) {
return x;
}
// Else try next number
x++;
}
}
// Num array
const num = [3, 4, 5];
// Rem array
const rem = [2, 3, 1];
console.log("The smallest number that is divisible by");
console.log("the given remainders and numbers is " + findMinX(num, rem));
Maths for Data Structure and Algorithms (DSA) | A Complete Guide
Maths is a fundamental component of learning Data Structure and Algorithms, just like in programming. Maths is primarily used to evaluate the effectiveness of different algorithms. However, there are situations when the answer requires some mathematical understanding or the problem has mathematical characteristics and certain problems demand more than just code. They require a mathematical perspective and a recognition of patterns and characteristics that go beyond the syntax of programming languages. Therefore, understanding maths is essential to know data structures and algorithms. So here in this Maths Guide for Data Structure and Algorithms (DSA), we will be looking into some commonly used concepts of Maths in DSA.
Table of Content
- GCD and HCF (Euclidean Algorithm)
- Divisors of a number
- Prime numbers using Sieve of Eratosthenes
- Square root
- Modular Arithmetic
- Fast Power-Exponentiation by Squaring
- Factorial of a number
- Fibonacci Number
- Catalan Numbers
- Euler Totient Function
- Prime numbers & Primality Tests
- Prime Factorization & Divisors
- Chinese Remainder Theorem
- Practice Problems based on Maths for DSA
- Most Frequently Asked Questions (FAQs)