Core · Module 12
Mathematics for DSA & Bit Manipulation
Euclidean GCD, modular arithmetic, fast exponentiation, prime sieves, combinatorics (nCr), and O(1) bit manipulation tricks.
Every competitive programming and technical interview problem involving large counts, periodicity, primes, subsets, or compact state compression relies on number theory and bit manipulation. This module builds those foundations from the hardware ALU up.
- 1Euclidean GCD, Modular Arithmetic, and Binary ExponentiationPro — members onlyCompute greatest common divisors in logarithmic steps, prevent 64-bit overflow with modular arithmetic, and raise numbers to huge powers in O(log b) multiplications.18 min
- 2Prime Sieves (Eratosthenes & Linear Sieve) and Prime FactorizationPro — members onlyTest primality and factorize single integers in O(sqrt(n)), generate all primes up to n in O(n log log n) with the Sieve of Eratosthenes, and factorize 10^6 queries in O(log n) each using Smallest Prime Factors (SPF).18 min
- 3Combinatorics, Modular nCr, and the Pigeonhole PrinciplePro — members onlyCount permutations, combinations, and Catalan structures using precomputed factorials and inverse factorials in O(1) per query, and prove existence guarantees with the Pigeonhole Principle.18 min
- 4Bit Manipulation Tricks and Submask EnumerationPro — members onlyClear lowest set bits with Brian Kernighan's n & (n - 1), isolate lowest set bits with n & -n, cancel pairs with XOR, and iterate over all submasks in O(3^k) total time.18 min