dsa3 min read
Plus One — Carry Propagation Array Trick [Easy Interview Problem]
Increment a large integer represented as an array by one. Learn the carry propagation pattern with O(n) solutions in C, C++, Java, JavaScript and Python.
Read →
Math
34 articles
dsa3 min read
Count Primes — Sieve of Eratosthenes O(n log log n) [Amazon Easy]
Count the number of prime numbers strictly less than n. Master the Sieve of Eratosthenes — one of the most elegant algorithms in CS — with full code in C, C++, Java, JavaScript and Python.
Read →
dsa1 min read
Missing Number [Medium] — Math Sum / XOR Trick
Find the missing number in [0..n] using the Gauss sum formula or XOR in O(n) time O(1) space.
Read →
dsa1 min read
Minimum Moves to Equal Array Elements II [Medium] — Median Target
Find the minimum total moves to make all array elements equal by targeting the median value.
Read →
dsa1 min read
Max Points on a Line [Hard] — Slope HashMap
Find the maximum number of points on the same line using a slope-as-fraction HashMap for each anchor point.
Read →
dsa1 min read
Sqrt(x) — Right Boundary Binary Search
Compute integer square root using right-boundary binary search to find the largest k where k*k <= x.
Read →
dsa1 min read
Maximum Value at Given Index — Binary Search on Peak Value
Maximize nums[index] given array length n, sum constraint maxSum, and each element >= 1 using binary search on the peak value.
Read →
dsa1 min read
Valid Perfect Square — Binary Search or Math
Check if a number is a perfect square in O(log n) using binary search or by exploiting odd-number sum identity.
Read →
dsa1 min read
Minimum Speed to Arrive on Time — BS on Train Speed
Find the minimum train speed to arrive on time given n rides (last ride doesn't wait) using binary search on speed.
Read →
dsa2 min read
Happy Number [Easy] — HashSet Cycle Detection
Determine if a number is happy by repeatedly summing digit squares and detecting cycles using a HashSet or Floyd algorithm.
Read →
dsa2 min read
Fraction to Recurring Decimal — Remainder Tracking HashMap
Convert a fraction to decimal string with recurring part detected via remainder position tracking.
Read →
dsa1 min read
Evaluate Reverse Polish Notation — Operand Stack
Evaluate an RPN expression by pushing numbers and applying operators to the top two stack elements.
Read →
dsa1 min read
Score of Parentheses — Stack Depth Doubling
Calculate the score of balanced parentheses where () = 1 and AB = A+B and (A) = 2*A using a stack depth trick.
Read →
dsa4 min read
Math & Number Theory Master Recap: Interview Cheatsheet
Complete reference for math and number theory DSA patterns: algorithm selection guide, complexity table, and top 25 interview problems.
Read →
dsa4 min read
Inclusion-Exclusion Principle: Counting with Overlaps
Apply the inclusion-exclusion principle to count elements satisfying union of conditions. Solves divisibility, coverage, and derangement problems.
Read →
dsa3 min read
Randomized Algorithms: Reservoir Sampling and Quickselect
Master randomized DSA algorithms: reservoir sampling for streams, quickselect for O(n) kth element, and random shuffling.
Read →
dsa3 min read
Game Theory: Nim, Grundy Numbers, and Sprague-Grundy
Master combinatorial game theory: Nim XOR strategy, Grundy (nimber) values, and Sprague-Grundy theorem for composite games.
Read →
dsa3 min read
Computational Geometry: Points, Lines, and Convex Hull
Tackle geometry problems in coding interviews: cross product, point-in-polygon, line intersection, and Graham scan convex hull.
Read →
dsa3 min read
Probability and Expected Value in Competitive Programming
Apply probability theory and expected value DP to competitive programming: dice problems, random walks, and geometric distribution.
Read →
dsa3 min read
Integer Overflow, Precision, and Safe Arithmetic
Prevent integer overflow in competitive programming: safe multiplication, __int128, binary search on answers, and floating-point gotchas.
Read →
dsa3 min read
Square Root Decomposition: Range Queries in O(sqrt n)
Build range query structures in O(sqrt n) per query with block decomposition. Simpler alternative to segment trees.
Read →
dsa3 min read
Chinese Remainder Theorem: Solving Modular Equations
Solve systems of modular congruences with the Chinese Remainder Theorem. Fundamental for cryptography and competitive math.
Read →
dsa3 min read
Number Sequences: Fibonacci Variants and Mathematical Patterns
Explore classic number sequences: Fibonacci, Lucas, Pell, tribonacci, with DP and matrix approaches.
Read →
dsa3 min read
Bit Manipulation: XOR Tricks and Bitmasking
Master bitwise operations for DSA: XOR tricks, Brian Kernighan bit counting, subset enumeration, and bitmask DP.
Read →
dsa3 min read
Matrix Exponentiation: Fibonacci and Linear Recurrences
Solve linear recurrences like Fibonacci in O(log n) using matrix exponentiation. Essential for DP optimization on large n.
Read →
dsa3 min read
Number Theory: Perfect Numbers, Abundant, and Digit Problems
Explore digit manipulation, perfect/abundant numbers, Armstrong numbers, and common math interview patterns.
Read →
dsa3 min read
Combinatorics: nCr, Pascal's Triangle, and Catalan Numbers
Compute combinations nCr efficiently with precomputed factorials, Pascal's triangle for small n, and Catalan numbers for tree/parenthesis counting.
Read →
dsa3 min read
Euler's Totient Function and Applications
Compute Euler's totient phi(n) for cryptography and modular inverse applications. Sieve variant for all values up to n.
Read →
dsa3 min read
Prime Factorization: Trial Division and Pollard's Rho
Factor integers efficiently with trial division O(sqrt n), SPF sieve O(log n), and understand when each approach is optimal.
Read →
dsa4 min read
Modular Arithmetic: Fast Exponentiation and Inverse
Master modular arithmetic for competitive programming: binary exponentiation O(log n), modular inverse, and Chinese Remainder Theorem.
Read →
dsa4 min read
GCD, LCM, and Extended Euclidean Algorithm
Master GCD/LCM with Euclidean algorithm O(log n) and the Extended Euclidean for modular inverse computation.
Read →
dsa3 min read
Sieve of Eratosthenes: Find All Primes Efficiently
Generate all primes up to n in O(n log log n) with the Sieve of Eratosthenes. Includes segmented sieve and prime factorization variants.
Read →
dsa2 min read
Math & Number Theory for DSA: Complete Guide
Master mathematical algorithms for DSA: primes, GCD, modular arithmetic, combinatorics, and fast exponentiation with 5-language implementations.
Read →
next js3 min read
Deriving the OLS Estimator
How to derive the OLS Estimator with matrix notation and a tour of math typesetting using markdown with the help of KaTeX.
Read →