Open In App

Maths for Data Structure and Algorithms (DSA) | A Complete Guide

Last Updated : 31 May, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

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.

DSA-for-maths-banner

1) GCD and HCF (Euclidean Algorithm)

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); }

2) Divisors of a number

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"; }

Java

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); } }

Python

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)

C#

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

// 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

3) Prime numbers using Sieve of Eratosthenes

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.

  1. Create a list of numbers from 2 to the desired limit.
  2. Start with the first number (2) and mark it as prime.
  3. Eliminate all multiples of the current prime number from the list.
  4. Find the next unmarked number in the list and set it as the new prime.
  5. Repeat steps 3-4 until the square of the current prime is greater than the limit.
  6. 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; }

Java

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); } }

Python

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

C#

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 + " "); } } } }

JavaScript

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);


Output

Prime numbers up to 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

4) Square root

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; }

Java

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 } }

Python

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

JavaScript

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


Output

4 4

5) Modular Arithmetic

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

Modular Inverse

  • 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.

6) Fast Power-Exponentiation by Squaring

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; }

Java

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)); } }

Python

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))

JavaScript

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();


Output

59049

7) Factorial of a number

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

8) Fibonacci Number

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

9) Catalan Numbers

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; }

Java

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

Python

# 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}")

JavaScript

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();


Output

The 5th Catalan number is: 42

10) Euler Totient Function

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; }

Java

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(); } }

Python

# 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()

JavaScript

// 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();

11) Prime numbers & Primality Tests

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.

12) Prime Factorization & Divisors

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; }

Java

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); } }

Python

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)

JavaScript

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);

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: [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; }

Java

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.

Python

# 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

JavaScript

// 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:

Problem

Link

Prime Numbers

Solve

Basic and Extenden Euclidean Algorithm

Solve

Factorial

Solve

LCM and GCD

Solve

Nth Fibonacci Number

Solve

Program to multiply two matrices

Solve

Nth catalan number

Solve

Write program to calculate pow(x, n)

Solve

Find all factors of a Natural Number

Solve

Modular Exponentiation

Solve

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.



Similar Reads

Data Structures &amp; Algorithms (DSA) Guide for Google Tech interviews
Google is known for its rigorous and highly competitive technical interviews. These interviews are designed to assess a candidate's problem-solving abilities, technical knowledge, and cultural fit with the company. Preparing for technical interviews at top companies like Google requires a solid understanding of Data Structures and Algorithms (DSA).
9 min read
Top 100 Data Structure and Algorithms DSA Interview Questions Topic-wise
DSA has been one of the most popular go-to topics for any interview, be it college placements, software developer roles, or any other technical roles for freshers and experienced to land a decent job. If you are among them, you already know that it is not easy to find the best DSA interview questions among the vast pool of available problems. So he
4 min read
What is DSA | DSA Full Form
What is DSA?DSA(Data Structures and Algorithms) is defined as a combination of two separate yet interrelated topics – Data Structure and Algorithms. DSA is one of the most important skills that every computer science student must have. It is often seen that people with good knowledge of these technologies are better programmers than others and thus
2 min read
Real-life Applications of Data Structures and Algorithms (DSA)
You may have heard that DSA is primarily used in the field of computer science. Although DSA is most commonly used in the computing field, its application is not restricted to it. The concept of DSA can also be found in everyday life. Here we'll address the common concept of DSA that we use in our day-to-day lives. Application of DataStructure Appl
10 min read
Learn DSA with Python | Python Data Structures and Algorithms
This tutorial is a beginner-friendly guide for learning data structures and algorithms using Python. In this article, we will discuss the in-built data structures such as lists, tuples, dictionaries, etc, and some user-defined data structures such as linked lists, trees, graphs, etc, and traversal as well as searching and sorting algorithms with th
15+ min read
What to do if I get stuck in Data Structures and Algorithms (DSA)?
Learning Data Structures and Algorithms is like a big adventure where you explore various techniques that tell us how to solve complex problems in computer science. It's like solving a puzzle where you might not be sure what piece goes where. Thus there are times when you might feel stuck while learning DSA. This blog will help to overcome those di
4 min read
Most Asked Problems in Data Structures and Algorithms | Beginner DSA Sheet
In this Beginner DSA Sheet for Data Structures and Algorithms, we have curated a selective list of problems for you to solve as a beginner for DSA. After learning the fundamentals of programming, choosing a programming language, and learning about Data Structure and Algorithms and their space-time complexity, it becomes necessary to practice the pr
3 min read
Data Structures and Algorithms (DSA) MCQ Quiz Online
Welcome to our Data Structures and Algorithms (DSA) MCQ Quiz Online! This DSA MCQ is all about Quizzes for solving problems and learning the fundamentals of Algorithms and Data Structures. You'll see multiple-choice questions (MCQs) that test how well you understand the basics and Data structure Algorithms. We'll cover every topic of DSA like Array
4 min read
Static Data Structure vs Dynamic Data Structure
Data structure is a way of storing and organizing data efficiently such that the required operations on them can be performed be efficient with respect to time as well as memory. Simply, Data Structure are used to reduce complexity (mostly the time complexity) of the code. Data structures can be two types : 1. Static Data Structure 2. Dynamic Data
4 min read
A Quick Guide on DSA and Competitive Coding in Java
Data Structures and Algorithms (DSA) are the building blocks of efficient and optimized software solutions, especially in the realm of competitive coding. In this quick guide, we'll explore key concepts of DSA using Java, a versatile and widely used programming language. Table of Content Arrays In Java:Strings In Java:Stack in Java:Queue in Java: L
11 min read
Article Tags :
Practice Tags :
three90RightbarBannerImg