Basic Math Concepts for DSA

Mathematical concepts form the foundation of many algorithms. Understanding these basics will help you solve complex problems efficiently, especially in competitive programming and technical interviews.

Number Systems

Decimal, Binary, and Other Bases

Computers work in binary (base-2), while humans use decimal (base-10). Understanding how to convert between them is fundamental.

# Decimal (base 10): 0-9
decimal = 42

# Binary (base 2): 0-1
binary = 0b101010  # Same as 42
print(bin(42))     # Output: '0b101010'

# Hexadecimal (base 16): 0-9, A-F
hex_num = 0x2A     # Same as 42
print(hex(42))     # Output: '0x2a'

Example: Base Conversion

Prime Numbers

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

Primality Test

The naive approach checks divisibility from 2 to n-1. A better approach checks up to sqrt(n).

Sieve of Eratosthenes

An efficient algorithm to find all primes up to a given limit n. It works by iteratively marking multiples of each prime starting from 2. Time Complexity: O(n log(log n))

Example: Primes and Sieve

GCD and LCM

Greatest Common Divisor (GCD)

The largest positive integer that divides two numbers without a remainder. Euclidean Algorithm: Efficiently computes GCD. Formula: GCD(a, b) = GCD(b, a % b)

Least Common Multiple (LCM)

The smallest positive integer that is divisible by both numbers. Formula: LCM(a, b) = (a * b) / GCD(a, b)

Example: GCD and LCM

Modular Arithmetic

Calculations involving the remainder when divided by a modulus m. Key properties:

1. (a + b) % m = ((a % m) + (b % m)) % m
2. (a * b) % m = ((a % m) * (b % m)) % m
3. (a - b) % m = ((a % m) - (b % m) + m) % m

This is essential in competitive programming to prevent integer overflow.

Example: Divisibility Rules & Factors

Key Takeaways

✅ Binary/Decimal conversion is fundamental for bitwise ops
✅ Sieve of Eratosthenes is the go-to for finding primes up to N
✅ GCD/LCM relationships help solve periodicity problems
✅ Modulo arithmetic prevents overflow in large calculations

Quiz