Summary of "Basic Maths for DSA | Euclidean Algorithm | Strivers A2Z DSA Course"

Summary of “Basic Maths for DSA | Euclidean Algorithm | Strivers A2Z DSA Course”

This video is part of the Strivers A2Z DSA course, focusing on foundational mathematical concepts essential for data structures and algorithms (DSA). The instructor emphasizes starting with basic math concepts before moving to advanced topics to build a strong foundation. The video covers digit extraction, counting digits, reversing numbers, checking palindromes, Armstrong numbers, printing divisors, checking prime numbers, and the Euclidean algorithm for GCD/HCF.

Main Ideas and Concepts Covered

1. Digit Extraction Concept

Extract digits from a number using modulo and division by 10.
Modulo 10 gives the last digit.
Integer division by 10 removes the last digit.
Digits are extracted in reverse order.

Pseudocode:

while (n > 0) {
    digit = n % 10;
    print(digit);
    n = n / 10;
}

This concept is fundamental for solving many problems involving digits.

2. Counting Digits

Use digit extraction to count how many digits a number has.
Increment a counter each time a digit is extracted until the number reduces to zero.
Alternative method: Use logarithm base 10.
- count = floor(log10(n)) + 1
Time complexity: O(log₁₀ n)

3. Reversing a Number

Extract digits and build the reverse number by: reverse_num = reverse_num * 10 + last_digit
Example: For 7789, reverse is 9877.
Trailing zeros in the original number disappear in the reverse.

4. Check Palindrome Number

A number is palindrome if it reads the same forwards and backwards.
Steps:
- Store original number in a variable.
- Reverse the number using the method above.
- Compare reversed number with original.
- Print true if equal, false otherwise.

5. Armstrong Number

A number is Armstrong if the sum of cubes of its digits equals the number itself.
Example: 371 = 3³ + 7³ + 1³
Use digit extraction to sum cubes of digits.
Compare sum with original number.

6. Print All Divisors of a Number

Naive approach:
- Loop from 1 to n.
- Print i if n % i == 0.
- Time complexity: O(n)
Optimized approach:
- Loop from 1 to √n.
- If i divides n, print i and n/i (if distinct).
- Store divisors in a list/vector and sort before printing for ordered output.
- Time complexity: O(√n + k log k), where k is number of divisors.
Use i*i <= n instead of calling sqrt() repeatedly for efficiency.

7. Check Prime Number

Definition: A prime number has exactly two factors: 1 and itself.
Brute force approach:
- Count factors by looping from 1 to n.
- Check if count == 2 → prime.
- Time complexity: O(n)
Optimized approach:
- Loop from 1 to √n.
- Check divisibility.
- Time complexity: O(√n)

8. Greatest Common Divisor (GCD) / Highest Common Factor (HCF)

GCD is the largest number that divides two numbers.
Brute force approach:
- Loop from 1 to min(n1, n2).
- Check if i divides both.
- Keep track of the largest such i.
- Time complexity: O(min(n1, n2))
Improved brute force:
- Loop backward from min(n1, n2) down to 1.
- Break on first common divisor found.
Euclidean Algorithm (Efficient GCD):
- Based on the property: gcd(a, b) = gcd(a - b, b) if a > b.
- Optimized using modulo: gcd(a, b) = gcd(b, a % b)
- Repeat until one number becomes zero.
- The other number is the GCD.
- Time complexity: O(log(min(a, b))) (logarithmic)
- This is much faster than brute force.

Methodologies / Instructions

Digit Extraction:
- Use digit = n % 10 to get last digit.
- Use n = n / 10 (integer division) to remove last digit.
- Repeat until n becomes zero.
Counting Digits:
- Initialize counter = 0.
- While n > 0:
  - counter++
  - n = n / 10
- Return counter.
- Or use logarithmic formula.
Reverse Number:
- Initialize reverse_num = 0.
- While n > 0:
  - last_digit = n % 10
  - reverse_num = reverse_num * 10 + last_digit
  - n = n / 10
- Return reverse_num.
Palindrome Check:
- Store original number in duplicate.
- Reverse the number using above method.
- Compare reverse_num with duplicate.
- Return true if equal, else false.
Armstrong Number:
- Initialize sum = 0.
- Extract each digit.
- Add cube of digit to sum.
- Compare sum with original number.
Print Divisors (Optimized):
- Loop i from 1 to √n:
  - If n % i == 0:
    - Add i to list.
    - If n/i != i, add n/i to list.
- Sort list.
- Print all elements.
Check Prime (Optimized):
- If n <= 1, not prime.
- Loop i from 2 to √n:
  - If n % i == 0, not prime.
- Else prime.
GCD (Euclidean Algorithm):
- While both a and b > 0:
  - If a > b: a = a % b
  - Else: b = b % a
- Return a or b (whichever is non-zero).

Time Complexity Highlights

Digit extraction / counting digits: O(log₁₀ n)
Reversing number: O(log₁₀ n)
Armstrong number check: O(log₁₀ n)
Printing divisors:
- Naive: O(n)
- Optimized: O(√n + k log k), where k = number of divisors
Prime check:
- Naive: O(n)
- Optimized: O(√n)
GCD:
- Brute force: O(min(n1, n2))
- Euclidean algorithm: O(log(min(n1, n2)))

Speakers / Sources Featured

Striver (Main Instructor / Speaker)

This video provides a comprehensive introduction to basic math concepts frequently used in DSA problems, emphasizing understanding through digit extraction and mathematical observations, culminating in the efficient Euclidean algorithm for GCD.