Striver's A to Z DSA Course: Basic Maths

Course Overview

• India’s most in-depth DS Algo course with 455 modules.
• Previous videos covered step 1.1 and 1.2.
• More resources available on YouTube for immediate needs.
• Teaching method starts with basics and gradually moves to advanced concepts.

Basic Maths Concepts

Digit Extraction Concepts

• Importance: Key concept for solving many basic math problems.
• Steps for Extraction:
  • Example given: 7789
  • Extract digits: 9, 8, 7, 7.
  • Use modulo 10 and integer division by 10 to get digits and reduce the number.
• Pseudocode:
  • While loop to ensure number is greater than zero.
  • Use modulo 10 to get last digit and integer division to reduce number.
• Output: Digits in reverse order.

Practical Applications of Digit Extraction

Problem 1: Count Digits

• Task: Count the number of digits in a given number.
• Solution: Use digit extraction method and count iterations.
• Alternative Solution: Use logarithm (log base 10) to find the number of digits quickly.
• Time Complexity: O(log base 10 n).

Problem 2: Reverse a Number

• Task: Reverse the digits of a given number.
• Solution:
  • Use digit extraction and form the reverse number by multiplying the existing reverse number by 10 and adding the extracted digit.
• Example:
  • Number: 7789 -> Reverse: 9877.
• Pseudo Code: Use a while loop and manage digits using multiplication and addition.

Problem 3: Check Palindrome

• Task: Check if a number is a palindrome.
• Solution:
  • Generate the reverse of the number and compare it with the original number.
  • Ensure to store the original number before modifying it.

Problem 4: Check Armstrong Number

• Task: Check if a number is an Armstrong number.
• Solution:
  • Extract digits and compute the sum of the cubes of digits.
  • Compare the sum with the original number.
  • Use previous extraction method to extract digits.

Problem 5: Print All Divisors

• Task: Print all divisors of a number in sorted order.
• Solution:
  • Initial solution: Check all numbers from 1 to n if they are divisors, if yes, print them.
  • Optimized solution: Check only up to the square root of n and manage pairs of divisors.
  • Store divisors in a list and sort to keep them in order.
• Time Complexity: O(sqrt(n)) for optimally finding the divisors.

Problem 6: Check for Prime Number

• Task: Check if a number is a prime number.
• Definition: A number that has exactly two factors: 1 and itself.
• Solution:
  • Initial Brute Force method: Check all numbers from 1 to n as potential factors.
  • Optimized solution: Check only up to the square root of n.
• Time Complexity: O(sqrt(n)) for the optimized approach.

Problem 7: GCD or HCF

• Task: Determine the Greatest Common Divisor (GCD) of two numbers.
• Initial Solution: Find all factors of both numbers and check for the greatest common factor.
• Optimized Solution: Use Euclidean algorithm.
  • Subtract the smaller number from the larger one, or use modulo operation to minimize steps.
  • Continue until one number becomes zero; the other number is the GCD.
• Time Complexity: O(log(min(a, b))).
• Improvement: Use a modulo operation instead of subtraction to improve efficiency.

Next Steps

• Watch videos on basic recursion added to the playlist.
• Upcoming topic: Basic Hashing.
• Encouragement to engage, subscribe, and continue learning.