🟢 Greedy Algorithms, Number Theory & Bit Manipulation (Coding)
Day 3 | ⏱️ 2.5 Hours | TCS Interview Prep
📌 Subtopics
Greedy Algorithms
- Activity selection problem
- Fractional knapsack
- Minimum coins for change
- Job sequencing
- Key idea: Make locally optimal choices at each step
Number Theory
- Prime numbers & Sieve of Eratosthenes
- GCD (Euclidean algorithm)
- LCM using GCD
- Modular arithmetic
Bit Manipulation
- AND, OR, XOR, NOT, Left/Right Shift
- Check if a number is power of 2
- Count set bits
- Toggle, set, clear a specific bit
🌐 Learning Resources
| Resource | Link |
|---|---|
| GFG — Greedy Algorithms | geeksforgeeks.org |
| GFG — Number Theory | geeksforgeeks.org |
| GFG — Bit Manipulation | geeksforgeeks.org |
| GFG — Sieve of Eratosthenes | geeksforgeeks.org |
| NeetCode — Greedy | neetcode.io |
| LeetCode — Greedy Tag | leetcode.com |
| LeetCode — Bit Manipulation Tag | [leetcode.com/tag/bit-manipulation/) |
✅ Must-Practice Problems (LeetCode)
| Problem | Difficulty | Link |
|---|---|---|
| Jump Game | Medium | leetcode.com/problems/jump-game |
| Coin Change (Greedy approach) | Medium | leetcode.com/problems/coin-change |
| Count Primes | Medium | leetcode.com/problems/count-primes |
| Power of Two | Easy | leetcode.com/problems/power-of-two |
| Number of 1 Bits | Easy | leetcode.com/problems/number-of-1-bits |
| Single Number (XOR) | Easy | leetcode.com/problems/single-number |
📝 Key Patterns
# Sieve of Eratosthenes
def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i in range(n+1) if is_prime[i]]
# GCD (Euclidean)
def gcd(a, b):
while b:
a, b = b, a % b
return a
# LCM
def lcm(a, b):
return a * b // gcd(a, b)
# Bit Manipulation
n & (n-1) == 0 # Check power of 2
n & 1 # Check odd/even
n >> 1 # Divide by 2
n << 1 # Multiply by 2
a ^ a == 0 # XOR same number = 0
bin(n).count('1') # Count set bits🔗 Related Topics
- Number System HCF LCM — Core math concepts for GCD, LCM, divisibility, and prime numbers
- Arrays and Hashing — Array representation of primes, hash maps for modular calculation caching
- Dynamic Programming — Knapsack and Coin Change optimization (when greedy choices fail)
- Series and Progressions — Arithmetic/geometric progressions and series sum identities
- Patterns and Series — Binary sequences, bitwise shift coding, and symbol/number patterns