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.
The GCD or HCF of two or more integers is the largest positive integer that divides each of the integers without leaving a remainder.
For example, let’s find the GCD/HCF of 12 and 18:
Factors of 12: 1, 2, 3, 4, 6, 12
Factors of 18: 1, 2, 3, 6, 9, 18
The common factors are 1, 2, 3, and 6. The largest among them is 6, so the GCD/HCF of 12 and 18 is 6.
- LCM(a,b) * GCD(a,b) = a*b
So, Now we have to calculate GCD of numbers , but how we do so ?
Euclid’s algorithm is an efficient method for calculating the GCD of two numbers. This algorithm uses the easy-to-prove fact gcd(a, b)=gcd(b, r), where r is the remainder when a is divided by b, or just a%b and keep on doing until b==0.
int GCD(int A, int B) {
if (B == 0)
return A;
else
return GCD(B, A % B); }
A divisor is a number that gives remainder as 0 when divided.
As we know the divisors of a number will definitely be lesser or equal to the number, all the numbers between 1 and the number, can be possible divisors of a number, but iterating through the entire number range takes O(n) time complexity, so can we optimize this approach?
The answer is YES it can be optimized to O(sqrt(n)) by careful observation, we can notice that the root of a number actually acts as a splitting part of all the divisors of a number.
Below is the code snippet for Divisors of a number:
C++
void printDivisorsOptimal(int n)
{
cout << "The Divisors of " << n << " are:" << endl;
for (int i = 1; i <= sqrt(n); i++)
if (n % i == 0) {
cout << i << " ";
if (i != n / i)
cout << n / i << " ";
}
cout << "\n";
}
import java.util.*;
public class PrintDivisorsOptimal {
// Function to print the divisors of a number 'n'
static void printDivisorsOptimal(int n) {
System.out.println("The Divisors of " + n + " are:");
// Iterate up to the square root of 'n'
for (int i = 1; i <= Math.sqrt(n); i++) {
// If 'i' divides 'n' evenly
if (n % i == 0) {
// Print the divisor 'i'
System.out.print(i + " ");
// If 'i' is not the square root of 'n', print the other divisor
if (i != n / i) {
System.out.print((n / i) + " ");
}
}
}
System.out.println(); // Print a new line after printing divisors
}
public static void main(String[] args) {
int num = 20; // Replace this number with the desired input
// Call the function to print divisors for the given number 'num'
printDivisorsOptimal(num);
}
}
import math
def print_divisors_optimal(n):
print("The Divisors of", n, "are:")
# Iterate up to the square root of 'n'
for i in range(1, int(math.sqrt(n)) + 1):
# If 'i' divides 'n' evenly
if n % i == 0:
# Print the divisor 'i'
print(i, end=" ")
# If 'i' is not the square root of 'n', print the other divisor
if i != n // i:
print(n // i, end=" ")
print() # Print a new line after printing divisors
if __name__ == "__main__":
num = 20 # Replace this number with the desired input
print_divisors_optimal(num)
using System;
class Program
{
static void PrintDivisorsOptimal(int n)
{
Console.WriteLine($"The Divisors of {n} are:");
for (int i = 1; i <= Math.Sqrt(n); i++)
{
if (n % i == 0)
{
Console.Write(i + " ");
if (i != n / i)
{
Console.Write(n / i + " ");
}
}
}
Console.WriteLine();
}
}
// JavaScript Implementation
function printDivisorsOptimal(n) {
console.log(`The Divisors of ${n} are:`);
for (let i = 1; i <= Math.sqrt(n); i++) {
if (n % i === 0) {
console.log(i);
if (i !== n / i) {
console.log(n / i);
}
}
}
}
const num = 20;
printDivisorsOptimal(num);
// This code is contributed by Sakshi
A prime number is a natural number greater than 1 and is divisible by only 1 and itself.
Generating primes fast is very important in some problems. You can use the Sieve of Eratosthenes to find all the prime numbers that are less than or equal to a given number N or to find out whether a number is a prime number in more efficient way.
The basic idea behind the Sieve of Eratosthenes is that at each iteration one prime number is picked up and all its multiples are eliminated. After the elimination process is complete, all the unmarked numbers that remain are prime.
- Create a list of numbers from 2 to the desired limit.
- Start with the first number (2) and mark it as prime.
- Eliminate all multiples of the current prime number from the list.
- Find the next unmarked number in the list and set it as the new prime.
- Repeat steps 3-4 until the square of the current prime is greater than the limit.
- All remaining unmarked numbers in the list are prime.
Below is the code snippet for Sieve of Eratosthenes:
C++
#include <iostream>
#include <vector>
using namespace std;
void sieve(int N) {
bool isPrime[N + 1];
for (int i = 0; i <= N; ++i) {
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
for (int i = 2; i * i <= N; ++i) {
// If i is prime
if (isPrime[i] == true) {
// Mark all the multiples of i as composite numbers
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// Print prime numbers
cout << "Prime numbers up to " << N << ": ";
for (int i = 2; i <= N; ++i) {
if (isPrime[i]) {
cout << i << " ";
}
}
cout << endl;
}
int main() {
// Limit the sieve to generate prime numbers up to 50
int N = 50;
sieve(N);
return 0;
}
import java.io.*;
public class GFG {
// Function to find prime numbers up to N using
// Sieve of Eratosthenes
public static void sieve(int N) {
// Create a boolean array to store prime flags for numbers up to N
boolean[] isPrime = new boolean[N + 1];
// Initialize all elements of the array as true
// assuming all numbers are prime initially
for (int i = 0; i <= N; ++i) {
isPrime[i] = true;
}
// 0 and 1 are not prime
// so mark them as false
isPrime[0] = false;
isPrime[1] = false;
// Iterate from 2 to the square root of N
for (int i = 2; i * i <= N; ++i) {
// If the current number is prime
if (isPrime[i]) {
// Mark all the multiples of i as composite numbers
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// Print prime numbers
System.out.println("Prime numbers up to " + N + ":");
for (int i = 2; i <= N; ++i) {
if (isPrime[i]) {
System.out.print(i + " ");
}
}
}
public static void main(String[] args) {
// Define the upper limit for finding prime numbers
int N = 50;
// Call the sieve function to find prime numbers up to N
sieve(N);
}
}
def sieve(N):
# Creating an array to store prime status of numbers from 0 to N
isPrime = [True] * (N + 1)
# Marking 0 and 1 as non-prime
isPrime[0] = False
isPrime[1] = False
# Iterating from 2 to sqrt(N)
for i in range(2, int(N ** 0.5) + 1):
# If current number is prime
if isPrime[i]:
# Marking multiples of i as non-prime
for j in range(i * i, N + 1, i):
isPrime[j] = False
# Print prime numbers
print("Prime numbers up to", N, ":")
for num, prime in enumerate(isPrime):
if prime:
print(num),
print("") # Empty print statement for newline
# Example usage:
N = 20 # Define the range for prime checking
sieve(N) # Call the function to sieve primes
using System;
public class Program {
// Declaring isPrime array outside of the Sieve method
private static bool[] isPrime;
public static void Sieve(int N)
{
isPrime = new bool[N + 1];
// Initializing all elements as true
for (int i = 0; i <= N; ++i) {
isPrime[i] = true;
}
isPrime[0] = false;
isPrime[1] = false;
// Iterate through numbers starting from 2 up to
// square root of N
for (int i = 2; i * i <= N; ++i) {
// If i is a prime number
if (isPrime[i]) {
// Mark all the multiples of i as composite
// numbers
for (int j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// At this point, isPrime array will contain true
// for prime numbers and false for composite numbers
}
public static void Main(string[] args)
{
int N
= 100; // Example: Find prime numbers up to 100
Sieve(N);
Console.WriteLine("Prime numbers up to " + N + ":");
for (int i = 2; i <= N; ++i) {
if (isPrime[i]) {
Console.Write(i + " ");
}
}
}
}
function sieve(N) {
// Create a boolean array to store prime flags for numbers up to N
let isPrime = new Array(N + 1).fill(true);
// 0 and 1 are not prime
// so mark them as false
isPrime[0] = false;
isPrime[1] = false;
// Iterate from 2 to the square root of N
for (let i = 2; i * i <= N; ++i) {
// If the current number is prime
if (isPrime[i]) {
// Mark all the multiples of i as composite numbers
for (let j = i * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
// Print prime numbers
let primes = [];
for (let i = 2; i <= N; ++i) {
if (isPrime[i]) {
primes.push(i);
}
}
console.log("Prime numbers up to " + N + ":");
console.log(primes.join(" ")); // Join prime numbers into a single string
//separated by space
}
// Define the upper limit for finding prime numbers
let N = 50;
// Call the sieve function to find prime numbers up to N
sieve(N);
OutputPrime numbers up to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
To find the floor of the square root, try with all-natural numbers starting from and continue incrementing the number until the square of that number is greater than the given number. but this will take linear time complexity .
So can we optimize to better complexity , answer is yes , the idea is to find the largest integer i whose square is less than or equal to the given number. The values of i*i is monotonically increasing, so the problem can be solved using binary search.
Below is the code snippet for Square root:
C++
#include <iostream>
int floorSqrt(int x)
{
// Base cases
if (x == 0 || x == 1)
return x;
// Do Binary Search for floor(sqrt(x))
int start = 1, end = x / 2, ans;
while (start <= end) {
int mid = (start + end) / 2;
// If x is a perfect square
int sqr = mid * mid;
if (sqr == x)
return mid;
if (sqr <= x) {
start = mid + 1;
ans = mid;
}
else end = mid - 1;
}
return ans;
}
int main() {
int num1 = 16;
int num2 = 17;
std::cout<< floorSqrt(num1) << std::endl;
std::cout << floorSqrt(num2) << std::endl;
return 0;
}
public class Main {
// Function to find the floor square root of a number
static int floorSqrt(int x) {
// Base cases
if (x == 0 || x == 1)
return x;
int start = 1, end = x / 2, ans = 0;
// Do Binary Search for floor(sqrt(x))
while (start <= end) {
int mid = start + (end - start) / 2;
// If x is a perfect square
int sqr = mid * mid;
if (sqr == x)
return mid;
if (sqr <= x) {
start = mid + 1;
ans = mid;
} else {
end = mid - 1;
}
}
return ans;
}
public static void main(String[] args) {
// Test the function
System.out.println(floorSqrt(16)); // Output: 4
System.out.println(floorSqrt(17)); // Output: 4
}
}
def floorSqrt(x):
# Base cases
if x == 0 or x == 1:
return x
start, end = 1, x // 2
ans = None
# Do Binary Search for floor(sqrt(x))
while start <= end:
mid = (start + end) // 2
# If x is a perfect square
sqr = mid * mid
if sqr == x:
return mid
if sqr <= x:
start = mid + 1
ans = mid
else:
end = mid - 1
return ans
# Test the function
print(floorSqrt(16)) # Output: 4
print(floorSqrt(17)) # Output: 4
function floorSqrt(x) {
// Base cases
if (x === 0 || x === 1)
return x;
let start = 1, end = Math.floor(x / 2), ans;
// Do Binary Search for floor(sqrt(x))
while (start <= end) {
let mid = Math.floor((start + end) / 2);
// If x is a perfect square
let sqr = mid * mid;
if (sqr === x)
return mid;
if (sqr <= x) {
start = mid + 1;
ans = mid;
} else {
end = mid - 1;
}
}
return ans;
}
// Test the function
console.log(floorSqrt(16)); // Output: 4
console.log(floorSqrt(17)); // Output: 4
Basically, modular arithmetic is related with computation of “mod” of expressions.
some important identities about the modulo operator:
- (a mod m) + (b mod m) mod m = a + b mod m
- (a mod m) – (b mod m) mod m = a – b mod m
- (a mod m) * (b mod m) mod m = a* b mod m
The modular division is totally different from modular addition, subtraction and multiplication. It also does not exist always.
- (a / b) mod m = (a x (inverse of b if exists)) mod m
- The modular inverse of a mod m exists only if a and m are relatively prime i.e. gcd(a, m) = 1. Hence, for finding the inverse of an under modulo m, if (a x b) mod m = 1 then b is the modular inverse of a.
We know how to find 2 raised to the power 10. But what if we have to find 2 raised to the power very large number such as 1000000000? Exponentiation by Squaring helps us in finding the powers of large positive integers. Idea is to the divide the power in half at each step.
9 ^ 5 = 9 * 9 * 9 * 9 * 9
// Try to divide the power by 2
// Since the power is an odd number here, we cannot do so.
// However there's another way to represent
9 ^ 59 ^ 5 = (9 ^ 4) * 9
// Now we can find 9 ^ 4 and later multiple the extra 9 to the result
9 ^ 5 = (81 ^ 2) * 9
Effectively, when power is not divisible by 2, we make power even by taking out the extra 9. Then we already know the solution when power is divisible by 2. Divide the power by 2 and multiply the base to itself.
Below is the code snippet for Fast Power-Exponentiation by Squaring
C++
#include <iostream>
int power(int x, int y, int p) {
// Initialize result
int res = 1;
// Update x if it is more than or equal to p
x = x % p;
// In case x is divisible by p
if (x == 0)
return 0;
while (y > 0) {
// If y is odd, multiply x with result
if (y % 2 == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
int main() {
// Find 9^5 mod 1000000007
std::cout << power(9, 5, 1000000007) << std::endl;
return 0;
}
public class Main {
static int power(int x, int y, int p)
{
// Initialize result
int res = 1;
// Update x if it is more than or equal to p
x = x % p;
// In case x is divisible by p
if (x == 0)
return 0;
while (y > 0) {
// If y is odd, multiply x with result
if ((y & 1) == 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
public static void main(String[] args)
{
// Find 9^5 mod 1000000007
System.out.println(power(9, 5, 1000000007));
}
}
def power(x, y, p):
# Initialize result
res = 1
# Update x if it is more than or equal to p
x = x % p
# In case x is divisible by p
if x == 0:
return 0
while y > 0:
# If y is odd, multiply x with result
if y & 1:
res = (res * x) % p
# y must be even now
y = y >> 1 # y = y/2
x = (x * x) % p
return res
print(power(9, 5, 1000000007))
function power(x, y, p) {
// Initialize result
let res = 1;
// Update x if it is more than or equal to p
x = x % p;
// In case x is divisible by p
if (x === 0)
return 0;
while (y > 0) {
// If y is odd, multiply x with result
if ((y & 1) === 1)
res = (res * x) % p;
// y must be even now
y = y >> 1; // y = y/2
x = (x * x) % p;
}
return res;
}
// Main method
function main() {
// Find 9^5 mod 1000000007
console.log(power(9, 5, 1000000007));
}
// Call the main method
main();
Factorial of a non-negative integer is the multiplication of all positive integers smaller than or equal to n. For example factorial of 6 is 6*5*4*3*2*1 which is 720.
Let’s create a factorial program using recursive functions. Until the value is not equal to zero, the recursive function will call itself. Factorial can be calculated using the following recursive formula.
n! = n * (n – 1)!
n! = 1 if n = 0 or n = 1
The Fibonacci series is the sequence where each number is the sum of the previous two numbers of the sequence. The first two numbers of the Fibonacci series are 0 and 1 and are used to generate the Fibonacci series.
In mathematical terms, the number at the nth position can be represented by:
Fn = Fn-1 + Fn-2
where, F0 = 0 and F1 = 1.
For example, Fibonacci series upto 10 terms is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34
Catalan numbers are a sequence of natural numbers that have various applications in combinatorial mathematics, particularly in the counting of different types of binary trees, parenthetical expressions, and more.
Formula: [Tex]C_n = \frac{1}{n+1}\binom{2n}{n}
[/Tex]
Below is the code snippet for Catalan Numbers:
C++
#include <iostream>
// Function to calculate nth Catalan number
unsigned long long catalan(unsigned int n)
{
if (n == 0 || n == 1)
return 1;
unsigned long long catalan_num = 0;
for (int i = 0; i < n; ++i)
catalan_num += catalan(i) * catalan(n - i - 1);
return catalan_num;
}
int main()
{
unsigned int n = 5;
unsigned long long result = catalan(n);
std::cout << "The " << n
<< "th Catalan number is: " << result
<< std::endl;
return 0;
}
public class Main {
// Function to calculate nth Catalan number
static long catalan(int n)
{
if (n == 0 || n == 1)
return 1;
long catalanNum = 0;
for (int i = 0; i < n; ++i)
catalanNum += catalan(i) * catalan(n - i - 1);
return catalanNum;
}
public static void main(String[] args)
{
int n = 5; // Example input
long nthCatalan = catalan(n);
System.out.println("The " + n
+ "th Catalan number is: "
+ nthCatalan);
}
}
// this code is contributed by Kishan
# Function to calculate nth Catalan number
def catalan(n):
# Base cases
if n == 0 or n == 1:
return 1
# Initialize result
catalan_num = 0
# Catalan number is the sum of catalan(i) * catalan(n - i - 1)
for i in range(n):
catalan_num += catalan(i) * catalan(n - i - 1)
return catalan_num
# Driver code
if __name__ == "__main__":
n = 5
result = catalan(n)
print(f"The {n}th Catalan number is: {result}")
function catalan(n) {
if (n === 0 || n === 1) {
return 1;
}
let catalanNum = 0;
for (let i = 0; i < n; ++i) {
catalanNum += catalan(i) * catalan(n - i - 1);
}
return catalanNum;
}
function main() {
const n = 5; // Example input
const nthCatalan = catalan(n);
console.log("The " + n + "th Catalan number is: " + nthCatalan);
}
main();
OutputThe 5th Catalan number is: 42
Euler’s Totient Function, denoted as ϕ(n), gives the count of positive integers less than or equal to n that are relatively prime to n.
Formula: [Tex]\phi(n) = n \left(1 – \frac{1}{p_1}\right)\left(1 – \frac{1}{p_2}\right)\ldots\left(1 – \frac{1}{p_k}\right)
[/Tex]
Below is the code snippet for Euler Totient Function:
C++
#include <iostream>
using namespace std;
// Function to return gcd of a and b
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
// A simple method to evaluate Euler Totient Function
int phi(unsigned int n) {
unsigned int result = 1; // Start with 1 because gcd(1, n) is always 1
for (int i = 2; i < n; i++) {
if (gcd(i, n) == 1) {
result++; // Increment result for every i that is coprime with n
}
}
return result;
}
// Example usage
int main() {
unsigned int n = 10; // Example value
cout << "Euler's Totient Function for " << n << " is " << phi(n) << endl;
return 0;
}
import java.util.Scanner;
public class EulerTotientFunction {
// Function to return gcd of a and b
public static int gcd(int a, int b) {
if (a == 0) {
return b;
}
return gcd(b % a, a);
}
// A simple method to evaluate Euler Totient Function
public static int phi(int n) {
int result = 1; // Start with 1 because gcd(1, n) is always 1
for (int i = 2; i < n; i++) {
if (gcd(i, n) == 1) {
result++; // Increment result for every i that is coprime with n
}
}
return result;
}
// Example usage
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = 10;
System.out.println("Euler's Totient Function for " + n + " is " + phi(n));
scanner.close();
}
}
# Function to return gcd of a and b
def gcd(a, b):
if a == 0:
return b
return gcd(b % a, a)
# A simple method to evaluate Euler Totient Function
def phi(n):
result = 1
for i in range(2, n):
if gcd(i, n) == 1:
result += 1
return result
# Example usage
def main():
n = 10
print("Euler's Totient Function for", n, "is", phi(n))
# Call the main function to execute the example usage
main()
// Function to return gcd of a and b
function gcd(a, b) {
if (a === 0)
return b;
return gcd(b % a, a);
}
// A simple method to evaluate Euler Totient Function
function phi(n) {
let result = 1;
for (let i = 2; i < n; i++) {
if (gcd(i, n) === 1) {
result++;
}
}
return result;
}
// Example usage
function main() {
let n = 10;
console.log("Euler's Totient Function for", n, "is", phi(n));
}
// Call the main function to execute the example usage
main();
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, a prime number is only divisible by 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13, and so on. Prime numbers play a crucial role in number theory and various areas of computer science, including cryptography and algorithm design.
Primality Tests:
Determining whether a given number is prime is a fundamental problem in number theory and computer science. Several algorithms and tests have been developed to check the primality of a number efficiently.
Prime Factorization: Expressing a number as a product of its prime factors.
Example: [Tex]\text{For } n = 24:
24 = 2^3 \times 3^1
[/Tex]
Divisors: The divisors of a number are the positive integers that divide the number without leaving a remainder.
Example: [Tex]\text{Divisors: } 1, 2, 3, 4, 6, 8, 12, 24.
[/Tex]
Below is the code snippet for Prime Factorization & Divisors:
C++
#include <iostream>
#include <cmath>
using namespace std;
void primeFactors(int n)
{
// Print the number of 2s that divide n
while (n % 2 == 0) {
cout << 2 << " ";
n /= 2;
}
// n must be odd at this point. So we can skip one
// element (Note i = i +2)
for (int i = 3; i <= sqrt(n); i += 2) {
// While i divides n, print i and divide n
while (n % i == 0) {
cout << i << " ";
n /= i;
}
}
// This condition is to handle the case when n is a
// prime number greater than 2
if (n > 2) {
cout << n;
}
}
// Test the function
int main()
{
primeFactors(315);
return 0;
}
import java.util.*;
public class Main {
public static void primeFactors(int n)
{
// Print the number of 2s that divide n
while (n % 2 == 0) {
System.out.print(2 + " ");
n /= 2;
}
// n must be odd at this point. So we can skip one
// element (Note i = i +2)
for (int i = 3; i <= Math.sqrt(n); i += 2) {
// While i divides n, print i and divide n
while (n % i == 0) {
System.out.print(i + " ");
n /= i;
}
}
// This condition is to handle the case when n is a
// prime number greater than 2
if (n > 2) {
System.out.print(n);
}
}
// Test the function
public static void main(String[] args)
{
primeFactors(315);
}
}
import math
def prime_factors(n):
# Print the number of 2s that divide n
while n % 2 == 0:
print(2, end=" ")
n = n / 2
# n must be odd at this point. So we can skip one element (Note i = i +2)
for i in range(3, int(math.sqrt(n)) + 1, 2):
# While i divides n, print i and divide n
while n % i == 0:
print(i, end=" ")
n = n / i
# This condition is to handle the case when n is a prime number greater than 2
if n > 2:
print(n, end=" ")
# Test the function
prime_factors(315)
function primeFactors(n) {
// Print the number of 2s that divide n
while (n % 2 === 0) {
process.stdout.write('2 ');
n /= 2;
}
// n must be odd at this point. So we can skip one element (Note i = i +2)
for (let i = 3; i <= Math.sqrt(n); i += 2) {
// While i divides n, print i and divide n
while (n % i === 0) {
process.stdout.write(`${i} `);
n /= i;
}
}
// This condition is to handle the case when n is a prime number greater than 2
if (n > 2) {
process.stdout.write(`${n}`);
}
}
// Test the function
primeFactors(315);
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: [Tex]x \equiv a_1M_1y_1 + a_2M_2y_2 + \ldots + a_kM_ky_k \pmod{M}
[/Tex]
Below is the code snippet for Chinese Remainder Theorem:
C++
// 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));
Practice Problems based on Maths for DSA:
Most Frequently Asked Questions (FAQs):
Question 1: Why is mathematics important for understanding Data Structures and Algorithms?
Answer: Mathematics is crucial for understanding Data Structures and Algorithms because it provides a formal language for analyzing and expressing the efficiency of algorithms. Mathematical concepts, such as discrete mathematics, enable precise reasoning about data structures and algorithmic complexities, leading to more effective problem-solving and optimized solutions.
Question 2: Which branches of mathematics are particularly relevant to DSA?
Answer: Branches of mathematics relevant to DSA include discrete mathematics, combinatorics, set theory, and graph theory. Understanding these areas is crucial for effective algorithm design and analysis.
Question 3: How does mathematical thinking enhance problem-solving skills in algorithm design?
Answer: Mathematical thinking enhances problem-solving skills in algorithm design by providing a structured approach to analyze and model complex problems. It cultivates logical reasoning, precision, and the ability to formulate algorithms with optimized solutions.
Question 4: Can I learn DSA without a strong mathematical background?
Answer: Yes, it’s possible to learn DSA without a strong mathematical background, but a basic understanding of key mathematical concepts can greatly enhance comprehension and problem-solving skills in algorithms.
Question 5: Why is set theory relevant to the study of algorithms?
Answer: Set theory provides a foundational framework for understanding data representation and manipulation in algorithms.
Question 6: How can mathematical skills enhance problem-solving in competitive programming and coding interviews?
Answer: Strong mathematical skills contribute to a more systematic and efficient approach to problem-solving, a key advantage in competitive programming and technical interviews.
Please Login to comment...