šŸ”¢ Day 9: Math Problems

Master Mathematical Algorithms for Coding Interviews

šŸ“š Core Mathematical Concepts

šŸŽÆ Prime Numbers

Definition: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Prime Check Optimization: Only test divisors up to āˆšn
Time Complexity: O(āˆšn) for single prime check
Space Complexity: O(1)
šŸ’” Interview Tip: Always check for n ā‰¤ 1, n = 2, and even numbers first before entering the loop.

šŸ“Š Sieve of Eratosthenes

Purpose: Find all prime numbers up to a given limit efficiently.

Mark multiples starting from iĀ² (not 2i) for optimization
Time Complexity: O(n log log n)
Space Complexity: O(n)

šŸ”¢ Factorial Problems

Basic Factorial

n! = n Ɨ (n-1) Ɨ (n-2) Ɨ ... Ɨ 1

Key Point: 0! = 1 by definition

Trailing Zeros

Count factors of 5 in n!

Why: Trailing zeros come from factors of 10 = 2 Ɨ 5, and there are always more factors of 2 than 5.

āš ļø Large Numbers: Factorial grows extremely fast. For n > 20, consider using modular arithmetic or special libraries.

šŸŒ€ Fibonacci Sequence

F(n) = F(n-1) + F(n-2), where F(0) = 0, F(1) = 1

Different Approaches:

  • Recursive: O(2āæ) - Exponential time, avoid in interviews!
  • Dynamic Programming: O(n) time, O(n) space
  • Optimized Iterative: O(n) time, O(1) space
  • Matrix Exponentiation: O(log n) time - Advanced technique
šŸ’” Golden Rule: Always use the iterative approach with two variables for interviews unless specifically asked for recursion.

šŸ”— GCD & LCM

Greatest Common Divisor (GCD)

gcd(a, b) = gcd(b, a mod b) - Euclidean Algorithm
Time Complexity: O(log min(a, b))
Space Complexity: O(1) iterative, O(log min(a, b)) recursive

Least Common Multiple (LCM)

lcm(a, b) = |a Ɨ b| / gcd(a, b)
āš ļø Overflow Protection: Calculate as (a / gcd(a, b)) Ɨ b to avoid integer overflow.

šŸŽ² Number Manipulation

šŸ”„Digit Reversal

Extract digits using modulo and integer division

while n > 0: digit = n % 10 result = result * 10 + digit n //= 10

āž•Digit Sum

Sum all digits in a number

sum(int(d) for d in str(n))

šŸ”¢Palindrome Check

Check if number reads same forwards and backwards

str(n) == str(n)[::-1]

šŸ’ŽPerfect Numbers

Number equals sum of its proper divisors

Example: 28 = 1 + 2 + 4 + 7 + 14

āš” Advanced Techniques

Fast Exponentiation

Problem: Calculate a^n efficiently

If n is even: a^n = (a^(n/2))Ā²
If n is odd: a^n = a Ɨ a^(n-1)
Time Complexity: O(log n) instead of O(n)

Newton's Method for Square Root

xā‚ = (xā‚€ + n/xā‚€) / 2

Iteratively refine the guess until desired precision

šŸŽÆ Interview Strategy

āš”Optimization Priority

  1. Correctness first
  2. Time complexity optimization
  3. Space complexity optimization
  4. Code readability

šŸšØCommon Edge Cases

  • Zero and negative inputs
  • Single digit numbers
  • Very large numbers
  • Empty or null inputs
šŸ’” Pro Tip: Always discuss your approach before coding. Mention the time/space complexity and any edge cases you're considering.

šŸ“ˆ Complexity Analysis Quick Reference

Prime Problems

  • Single prime check: O(āˆšn)
  • Sieve of Eratosthenes: O(n log log n)
  • Prime factorization: O(āˆšn)

Sequence Problems

  • Fibonacci (iterative): O(n)
  • Factorial: O(n)
  • GCD: O(log min(a,b))

šŸ”„ Key Takeaways

  • Master the fundamentals: GCD, prime check, factorial algorithms
  • Optimize ruthlessly: Always aim for the most efficient solution
  • Handle edge cases: Zero, negative numbers, and boundary conditions
  • Know multiple approaches: Iterative, recursive, mathematical shortcuts
  • Practice number theory: Divisibility, modular arithmetic, perfect squares