🏫 School Level Basics
One-line summary: Foundational mathematical and algorithmic building blocks — primes, GCD, palindromes, factorials, digit manipulation. Every DSA practitioner must write these from memory.
Diagram
Concept
These problems build your intuition for:
- Digit manipulation: extracting digits via
% 10andMath.floor(n/10) - Primality testing: trial division up to √n
- GCD / LCM: Euclidean algorithm —
gcd(a,b) = gcd(b, a%b) - Palindrome checking: two-pointer or reverse-half technique
- Bit tricks: XOR swap, power-of-two check
Key Algorithms
Euclidean GCD
function gcd(a, b) { return b === 0 ? a : gcd(b, a % b); }
function lcm(a, b) { return (a / gcd(a, b)) * b; }
Sieve of Eratosthenes
function sieve(n) {
const isPrime = new Array(n + 1).fill(true);
isPrime[0] = isPrime[1] = false;
for (let i = 2; i * i <= n; i++)
if (isPrime[i]) for (let j = i * i; j <= n; j += i) isPrime[j] = false;
return isPrime;
}
Digit Extraction
function sumDigits(n) {
let sum = 0;
while (n > 0) { sum += n % 10; n = Math.floor(n / 10); }
return sum;
}
XOR Swap (no temp variable)
let a = 5, b = 3;
a ^= b; b ^= a; a ^= b; // a=3, b=5
Complexity Summary
| Problem | Time | Space |
|---|---|---|
| Sum 1..N (formula) | O(1) | O(1) |
| Prime check (trial division) | O(√n) | O(1) |
| Sieve of Eratosthenes | O(n log log n) | O(n) |
| Factorial (iterative) | O(n) | O(1) |
| GCD (Euclidean) | O(log min(a,b)) | O(1) |
| Palindrome check | O(n) | O(1) |
Arrays — Key Concepts
Arrays are the most fundamental data structure: a contiguous block of memory with O(1) index access.
| Operation | Time | Notes |
|---|---|---|
| Access by index | O(1) | Random access |
| Search (unsorted) | O(n) | Linear scan |
| Search (sorted) | O(log n) | Binary search |
| Insert at end | O(1) amortized | Dynamic array |
| Insert at index | O(n) | Shift required |
| Delete at index | O(n) | Shift required |
Common pitfalls:
- Off-by-one errors (
<vs<=) - Mutating array while iterating
- Forgetting to handle empty array edge cases
Practice Problems
Related Topics
- Math — deeper number theory
- Bit Manipulation — XOR swap, parity tricks
- Two Pointers — palindrome with two pointers
← Back to Home · © sparshjaswal