Chapters 10 through 12. Spatial logic pushed to its limits: spiral matrices, fractals, and geometric shapes. The mathematical toolkit for competitive programming: SPF sieve, binary exponentiation, matrix expo, Euler's totient, and combinatorics. Advanced array strategies: 2D prefix sums, difference arrays, bitmask generation, sweep lines, and cycle-based sorting.
Generate the first N rows of Pascal's triangle. Do not use an O(N²) 2D array. Optimize space to O(N) by storing only the previous row to compute the next.
Every element in Pascal's Triangle is the sum of the two elements directly above it. Since row K only depends on row K-1, we don't need rows 0 to K-2 in memory. Maintain a single 1D array of size N and update it from right to left to avoid overwriting values we still need for the current iteration.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1
Row 1: [1]
Row 2: [1, 0] → j=1: arr[1]+=arr[0] → [1, 1]
Row 3: [1, 1, 0] → j=2: arr[2]+=arr[1] → [1, 1, 1]
→ j=1: arr[1]+=arr[0] → [1, 2, 1] Correct!void printPascal(int n) {
vector<int> row(n, 0);
row[0] = 1;
for (int i = 0; i < n; i++) {
// Print leading spaces for alignment
for (int s = 0; s < n - i - 1; s++) cout << " ";
// Update array right-to-left to prevent overwrite
for (int j = i; j > 0; j--)
row[j] = row[j] + row[j - 1];
// Print current row
for (int j = 0; j <= i; j++) cout << row[j] << " ";
cout << "\n";
}
}Time: O(N²) | Space: O(N). By collapsing the 2D matrix to a single 1D vector updated backwards, memory is drastically cut with zero correctness cost.
Given an integer N, print an N×N matrix filled with numbers from 1 to N² spiraling inward from the top-left corner.
N = 4Spiral matrix (see visual)Use four boundaries: top, bottom, left, right. A while loop contains four for loops representing the four traversal directions: Left→Right, Top→Bottom, Right→Left, Bottom→Top. After each directional pass, shrink the respective boundary inward.
1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7
Start: T=0, B=3, L=0, R=3 1. L→R: Fill 1,2,3,4. T++ (T=1) 2. T→B: Fill 5,6,7. R-- (R=2) 3. R→L: Fill 8,9,10. B-- (B=2) 4. B→T: Fill 11,12. L++ (L=1) Repeat for inner ring...
void generateSpiral(int n) {
vector<vector<int>> matrix(n, vector<int>(n));
int top = 0, bottom = n - 1, left = 0, right = n - 1;
int val = 1;
while (left <= right && top <= bottom) {
for (int i = left; i <= right; i++) matrix[top][i] = val++;
top++;
for (int i = top; i <= bottom; i++) matrix[i][right] = val++;
right--;
if (top <= bottom) {
for (int i = right; i >= left; i--) matrix[bottom][i] = val++;
bottom--;
}
if (left <= right) {
for (int i = bottom; i >= top; i--) matrix[i][left] = val++;
left++;
}
}
for (auto& row : matrix) {
for (int x : row) cout << setw(3) << x;
cout << "\n";
}
}Time: O(N²) | Space: O(N²). You MUST guard if(top <= bottom) and if(left <= right) before the reverse traversals (steps 3 and 4) to prevent double-filling on odd-sized matrices.
Given an N×N matrix, print its elements in a zig-zag diagonal order — the same traversal pattern used in JPEG compression quantization.
Group elements by their diagonal sum: row + col == k. The sum k ranges from 0 to 2*(N-1). If k is even, traverse the diagonal upward (decrease row, increase col). If k is odd, traverse downward. Clamp starting indices to remain within bounds.
[ 1 2 3 ] [ 4 5 6 ] [ 7 8 9 ] Output: 1, 2, 4, 7, 5, 3, 6, 8, 9
k=0 (Even, Up): (0,0)→1
k=1 (Odd, Down): (0,1)→2, (1,0)→4
k=2 (Even, Up): (2,0)→7, (1,1)→5, (0,2)→3
k=3 (Odd, Down): (1,2)→6, (2,1)→8
k=4 (Even, Up): (2,2)→9 Complete!void printZigZag(vector<vector<int>>& mat) {
int n = mat.size();
for (int s = 0; s <= 2 * (n - 1); s++) {
if (s % 2 == 0) {
// Traverse upward
int r = min(s, n - 1);
int c = s - r;
while (r >= 0 && c < n) { cout << mat[r][c] << " "; r--; c++; }
} else {
// Traverse downward
int c = min(s, n - 1);
int r = s - c;
while (c >= 0 && r < n) { cout << mat[r][c] << " "; r++; c--; }
}
}
cout << "\n";
}Time: O(N²) | Space: O(1). Visits each cell exactly once. The diagonal sum trick is reusable for any anti-diagonal traversal problem.
For a given N, print a concentric square where the outermost ring is N, the next ring is N-1, dropping until the center is 1. Grid size is always (2N-1) × (2N-1).
Instead of drawing rings sequentially, inspect every single cell (i, j). The value at any cell equals N − minDistance, where minDistance is its closest distance to any of the 4 borders. This collapses the entire problem into a single O(1) formula per cell.
4 4 4 4 4 4 4 4 3 3 3 3 3 4 4 3 2 2 2 3 4 4 3 2 1 2 3 4 4 3 2 2 2 3 4 4 3 3 3 3 3 4 4 4 4 4 4 4 4
Grid size = 2(4)-1 = 7. Top=0, Bottom=6.
Distance from top = i = 2
Distance from bottom = 6-i = 4
Distance from left = j = 3
Distance from right = 6-j = 3
Min distance = 2.
Value = N - minDist = 4 - 2 = 2 (matches the grid above)void concentricRectangles(int n) {
int size = 2 * n - 1;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
int top = i;
int bottom = size - 1 - i;
int left = j;
int right = size - 1 - j;
int distance = min({top, bottom, left, right});
cout << n - distance << " ";
}
cout << "\n";
}
}Time: O(N²) | Space: O(1). The topological distance formula eliminates any need to build the array in memory — the value is computed on the fly per cell.
Print the Swastika (Hindu cross) pattern using stars for a given odd dimension N. The pattern is built from four quadrant rules intersecting at the center axes.
The grid is divided into 4 quadrants by the center row and column (i == n/2 or j == n/2). For each of the four quadrants, a single additional edge line is drawn. Chain these checks in a single if condition.
* * * *
* *
* *
* * * * * * *
* *
* *
* * * * *Center Cross: print if (i == n/2) OR (j == n/2) Q1 (Top Left): print if (j == 0 AND i < n/2) Q2 (Top Right): print if (i == 0 AND j > n/2) Q3 (Bottom Left): print if (i == n-1 AND j < n/2) Q4 (Bottom Right): print if (j == n-1 AND i > n/2)
void swastika(int n) {
int mid = n / 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == mid || j == mid ||
(j == 0 && i < mid) || // Top-left vertical
(i == 0 && j > mid) || // Top-right horizontal
(i == n - 1 && j < mid) || // Bottom-left horizontal
(j == n - 1 && i > mid)) // Bottom-right vertical
cout << "* ";
else
cout << " ";
}
cout << "\n";
}
}Time: O(N²) | Space: O(1). N must be odd. An even value destroys the center-line symmetry and produces a malformed output.
Construct a right-facing Arrow of stars that peaks at width N then contracts, using a single loop from 1 to 2N-1.
Run a single loop from i = 1 to 2N-1. If i <= N, stars on that row = i. Otherwise, stars = 2N - i. This mirror formula completely avoids writing two separate expansion/contraction loops.
* ** *** **** *** ** *
i=1: i≤4 → 1 star
i=4: i≤4 → 4 stars (peak)
i=5: i>4 → 2(4)-5 = 3 stars Symmetric deflation begins
i=7: i>4 → 2(4)-7 = 1 starvoid rightArrow(int n) {
for (int i = 1; i < 2 * n; i++) {
int stars = (i <= n) ? i : (2 * n - i);
for (int j = 0; j < stars; j++) cout << "*";
cout << "\n";
}
}Time: O(N²) | Space: O(1). The 2N-1 iteration loop replaces two redundant halves with a single mirrored formula.
Print Pascal's Triangle for N rows, calculating each element via the combination formula C(i, j) — no array caching at all.
The element at row i, column j is literally C(i, j). Compute C(n, r) in O(r) by multiplying and dividing incrementally: res = res * (n-i) / (i+1). This avoids factorial overflow and never stores the triangle in memory.
Row 3 → C(3,0), C(3,1), C(3,2), C(3,3)
1, 3, 3, 1int nCr(int n, int r) {
long long res = 1;
if (r > n - r) r = n - r; // C(n,r) == C(n,n-r) optimization
for (int i = 0; i < r; i++) {
res *= (n - i);
res /= (i + 1);
}
return (int)res;
}
void printPascalMath(int n) {
for (int i = 0; i < n; i++) {
for (int s = 0; s < n - i - 1; s++) cout << " ";
for (int j = 0; j <= i; j++) cout << nCr(i, j) << " ";
cout << "\n";
}
}Time: O(N³) overall | Space: O(1). Calling nCr — which is O(r) — nested inside O(N²) rows makes the overall complexity cubic. Zero-memory but slower than the P93 caching approach. Choose based on whether memory or speed is the bottleneck.
Print a symmetrical butterfly. Wings expand from 1 to N stars, merge at row N, then identically mirror back to 1.
Every row has three zones: Left wing (i stars), Middle body (2*(N-i) spaces), Right wing (i stars). Phase 1 runs from 1 to N. Phase 2 iterates N-1 down to 1 using the exact same logic — no separate formula needed.
* * ** ** *** *** ******** ******** *** *** ** ** * *
void printButterfly(int n) {
// Upper half
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) cout << "*";
for (int s = 1; s <= 2 * (n - i); s++) cout << " ";
for (int j = 1; j <= i; j++) cout << "*";
cout << "\n";
}
// Lower half (same logic, reverse order)
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= i; j++) cout << "*";
for (int s = 1; s <= 2 * (n - i); s++) cout << " ";
for (int j = 1; j <= i; j++) cout << "*";
cout << "\n";
}
}Time: O(N²) | Space: O(1).
The inverse of a butterfly. Form a solid rectangle, but carve out an empty diamond-shaped void inside it.
Top half: Left stars shrink from N down to 1. Inner spaces expand from 0 up. By inverting the butterfly's expansion logic — stars shrink while spaces grow — the inner void becomes a perfect hollow diamond.
******** *** *** ** ** * * * * ** ** *** *** ********
void hollowDiamond(int n) {
// Upper cavity
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i; j++) cout << "*";
for (int j = 0; j < 2 * i; j++) cout << " ";
for (int j = 0; j < n - i; j++) cout << "*";
cout << "\n";
}
// Lower cavity (mirror)
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < n - i; j++) cout << "*";
for (int j = 0; j < 2 * i; j++) cout << " ";
for (int j = 0; j < n - i; j++) cout << "*";
cout << "\n";
}
}Time: O(N²) | Space: O(1). Inversion requires zero changes to asymptotic complexity.
Draw the capital letter "Z" on an N×N grid using stars — two horizontal borders and a diagonal slash.
Print a star at (i, j) if it is on the top row (i == 0), the bottom row (i == n-1), or on the anti-diagonal (i + j == n - 1). Three conditions. One pass.
***** * * * *****
void printZ(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || i == n - 1 || i + j == n - 1)
cout << "*";
else
cout << " ";
}
cout << "\n";
}
}Time: O(N²) | Space: O(1). The anti-diagonal condition i + j == n - 1 is the key formula — it is the complement of the main diagonal condition i == j.
Print a symmetrical heart shape of size N. The shape features two upper semi-circles over a downward-pointing inverted triangle.
Phase 1: Loop from N/2 to N step 2, printing two humps with a gap in the center. Phase 2: Print an inverted pyramid from width 2N-1 down to 1, indented from the left edge.
*** ***
***** *****
*************
***********
*********
*******
*****
***
*void printHeart(int n) {
// Top dual-curves (loop i from n/2 to n, step 2)
for (int i = n / 2; i <= n; i += 2) {
for (int s = 1; s < n - i; s += 2) cout << " "; // Left indent
for (int j = 1; j <= i; j++) cout << "*"; // Left hump
for (int s = 1; s <= n - i; s++) cout << " "; // Center cleft
for (int j = 1; j <= i; j++) cout << "*"; // Right hump
cout << "\n";
}
// Bottom inverted pyramid
for (int i = n; i >= 1; i--) {
for (int s = i; s < n; s++) cout << " ";
for (int j = 1; j <= (i * 2) - 1; j++) cout << "*";
cout << "\n";
}
}Time: O(N²) | Space: O(1). The upper loop uses i += 2. For small N (< 4), the rendering deforms. Ensure N ≥ 4 for a recognizable heart.
Draw a continuous oscillating sine-like wave across the screen for N peaks using only integer arithmetic — no sin() calls.
The wave fits in a fixed 3-row height. Use a modulo check: print a star at (i, j) if ((i + j) % 4 == 0) or (i == 2 && j % 4 == 0). This formula maps discrete amplitude points onto the grid mathematically, replacing float trigonometry entirely.
* * * * * * * * * * * * * * *
void printWave(int length) {
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= length; j++) {
if (((i + j) % 4 == 0) || (i == 2 && j % 4 == 0))
cout << "*";
else
cout << " ";
}
cout << "\n";
}
}Time: O(length) | Space: O(1). Pure cycle-modulo math replaces float sin(x) completely — no precision issues, no math.h dependency.
Print a number-based hourglass: numbers descend inward from the top, cross at zero, then expand back out symmetrically below.
Combine a downward contracting pyramid with an upward expanding one. Each row prints: leading spaces, numbers decreasing from i to 0, then numbers increasing from 1 to i. The first loop runs i from N down to 0; the second runs i from 1 up to N.
3 2 1 0 1 2 3
2 1 0 1 2
1 0 1
0
1 0 1
2 1 0 1 2
3 2 1 0 1 2 3void hourGlass(int n) {
for (int i = n; i >= 0; i--) {
for (int s = 0; s < n - i; s++) cout << " ";
for (int j = i; j >= 0; j--) cout << j << " ";
for (int j = 1; j <= i; j++) cout << j << " ";
cout << "\n";
}
for (int i = 1; i <= n; i++) {
for (int s = 0; s < n - i; s++) cout << " ";
for (int j = i; j >= 0; j--) cout << j << " ";
for (int j = 1; j <= i; j++) cout << j << " ";
cout << "\n";
}
}Time: O(N²) | Space: O(1).
Draw a solid parallelogram (rhombus) of width N, and a hollow variant using the same loop by adding a boundary condition.
A rhombus is a square where each successive row is offset by one additional leading space. The hollow variant simply checks boundary edges: print a star only if i == 0, i == N-1, j == 0, or j == N-1.
Solid: Hollow:
**** ****
**** * *
**** * *
**** ****void rhombusHollowSolid(int n, bool hollow) {
for (int i = 0; i < n; i++) {
for (int s = 0; s < n - i; s++) cout << " ";
for (int j = 0; j < n; j++) {
if (!hollow || i == 0 || i == n - 1 || j == 0 || j == n - 1)
cout << "*";
else
cout << " ";
}
cout << "\n";
}
}Time: O(N²) | Space: O(1). Parameterizing hollow keeps both variants in one function without code duplication.
Draw the Sierpinski fractal triangle using pure bitwise logic — no recursion, no matrices, no combinatorics.
A remarkable property of binary arithmetic: if (row & col) == col, the cell is part of the fractal. Equivalently, (row & col) == 0 for the standard left-aligned form. The Bitwise AND operation between a row index and column index directly maps the self-similar triangular structure with zero mathematical overhead.
* ** * * **** * * ** ** * * * * ********
row = 2 (binary: 0010): j=0 (0000): 2 & 0 = 0 → * (star) j=1 (0001): 2 & 1 = 0 → * (star) j=2 (0010): 2 & 2 = 2 → (empty) Output: * * ← matches the fractal!
void sierpinskiBitwise(int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
// The legendary fractal check: AND of row and col == 0
if ((i & j) == 0 || (i & ~j) == i)
cout << "* ";
else
cout << " ";
}
cout << "\n";
}
}Time: O(N²) | Space: O(1). To see the true fractal geometry, N must be a power of 2 (8, 16, 32, 64). Other values produce visually chopped outputs that truncate mid-fractal.
Given multiple queries for the prime factorization of a number N ≤ 10⁶, precompute an SPF array so each query runs in O(log N) instead of O(√N).
Modify the Sieve of Eratosthenes. Instead of storing isPrime[], store spf[] — the Smallest Prime Factor of every number. Initialize spf[i] = i. When you find a prime p, iterate through its multiples and if their SPF is still themselves, update it to p. To factorize X, repeatedly divide by spf[X] until X == 1.
i: 1 2 3 4 5 6 7 8 9 10 spf: 1 2 3 2 5 2 7 2 3 2
X=12. spf[12]=2. Factor: 2. X = 12/2 = 6.
X= 6. spf[ 6]=2. Factor: 2. X = 6/2 = 3.
X= 3. spf[ 3]=3. Factor: 3. X = 3/3 = 1.
Factors: [2, 2, 3] Terminates instantly!const int MAXN = 1000000;
int spf[MAXN + 1];
void sieveSPF() {
for (int i = 1; i <= MAXN; i++) spf[i] = i;
for (int i = 2; i * i <= MAXN; i++) {
if (spf[i] == i) { // i is prime
for (int j = i * i; j <= MAXN; j += i) {
if (spf[j] == j) spf[j] = i; // Assign smallest prime
}
}
}
}
void getFactorization(int x) {
cout << "Factors of " << x << ": ";
while (x != 1) {
cout << spf[x] << " ";
x = x / spf[x];
}
cout << "\n";
}Time: Precomputation O(N log log N), each query O(log N) | Space: O(N). Essential when answering 10⁵ factorization queries on large inputs cleanly.
Find (A⁻¹) mod M. Division under modulo is illegal — compute (A × B⁻¹) mod M instead using Fermat's Little Theorem.
If M is prime, Fermat's Little Theorem states A^(M-1) ≡ 1 (mod M). Multiplying both sides by A⁻¹ gives A^(M-2) ≡ A⁻¹ (mod M). So to find the inverse of A, compute A^(M-2) mod M using binary exponentiation.
Theorem: 3^(7-2) % 7 → 3^5 % 7
3^5 = 243. 243 % 7 = 5.
Check: (3 × 5) % 7 = 15 % 7 = 1. Correct! inv(3) under mod 7 is 5.long long power(long long base, long long exp, long long mod) {
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return res;
}
long long modInverse(long long n, long long m) {
// Only valid when m is prime (Fermat's Little Theorem)
return power(n, m - 2, m);
}
long long modDivide(long long a, long long b, long long m) {
a = a % m;
return (a * modInverse(b, m)) % m;
}Time: O(log M) | Space: O(1). Fermat's theorem strictly requires M to be prime (like 10⁹+7). If M is composite, use the Extended Euclidean Algorithm (P112) instead.
Calculate X^N mod M in O(log N) instead of O(N) — essential when N ≤ 10¹⁸ and iterative multiplication is infeasible.
Instead of multiplying X sequentially N times, use the binary representation of N. If N is even: X^N = (X^(N/2))². If N is odd: X^N = X × (X^(N/2))². Repeatedly square the base and halve the exponent — the number of multiplications collapses from N to log₂(N).
N=13 (Odd). Ans = 1×3 = 3. Base = 3×3 = 9. N = 6.
N= 6 (Even). Ans = 3. Base = 9×9 = 81. N = 3.
N= 3 (Odd). Ans = 3×81 = 43. Base = 81×81 = 61. N = 1.
N= 1 (Odd). Ans = 43×61 = 23. Base = ... N = 0.
Final Ans = 23. 3^13 computed in 4 multiplications, not 13!long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1) // If b is odd
res = (res * a) % m;
a = (a * a) % m; // Square the base
b >>= 1; // Halve the exponent
}
return res;
}Time: O(log N) | Space: O(1). The bitwise shift b >>= 1 and check b & 1 operate at CPU register level — this is as fast as software exponentiation gets.
Find the 1,000,000th Fibonacci number mod 10⁹+7. Standard DP iterates 10⁶ times. Use matrix exponentiation to reach it in O(log N).
The Fibonacci recurrence F(n) = F(n-1) + F(n-2) can be represented as matrix multiplication. The transformation matrix [[1,1],[1,0]] raised to the power N-1 using binary exponentiation on matrices gives F(N) at the top-left cell. The identity matrix acts as "1" for matrix multiplication.
[ F(N) ] = [ 1 1 ] ^ (N-1) × [ F(1) ] [ F(N-1) ] [ 1 0 ] [ F(0) ]
const int MOD = 1e9 + 7;
typedef vector<vector<long long>> Matrix;
Matrix multiply(Matrix A, Matrix B) {
Matrix C(2, vector<long long>(2, 0));
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
return C;
}
Matrix matpow(Matrix A, long long p) {
Matrix res = {{1, 0}, {0, 1}}; // Identity matrix
while (p > 0) {
if (p & 1) res = multiply(res, A);
A = multiply(A, A);
p >>= 1;
}
return res;
}
long long fibFast(long long n) {
if (n == 0) return 0;
Matrix T = {{1, 1}, {1, 0}};
T = matpow(T, n - 1);
return T[0][0]; // Top-left cell holds F(N)
}Time: O(M³ log N), Space: O(M²) where M=2 here. Apply the modulo strictly inside the multiply loop's addition — not outside — to prevent 64-bit overflow on intermediate products.
Given integers A and B, find coefficients x and y such that Ax + By = GCD(A, B). This is Bézout's identity.
Run the standard Euclidean algorithm recursively. On the way back up, derive the Bézout coefficients: the new x is the previous y1, and the new y is x1 - floor(A/B) * y1. The base case when B == 0 returns x=1, y=0.
gcd(30,20) → gcd(20,10) → gcd(10,0).
Base: x1=1, y1=0
Return 1: x = 0, y = 1 - (20/10)*0 = 1
Return 2: x = 1, y = 0 - (30/20)*1 = -1
Check: 30(1) + 20(-1) = 10. Correct! (x=1, y=-1)// Returns GCD and sets x, y such that a*x + b*y = gcd(a,b)
int extGCD(int a, int b, int& x, int& y) {
if (b == 0) { x = 1; y = 0; return a; }
int x1, y1;
int gcd = extGCD(b, a % b, x1, y1);
// Back-substitution
x = y1;
y = x1 - (a / b) * y1;
return gcd;
}Time: O(log min(A,B)) | Space: O(log min(A,B)) stack frames. Use this instead of Fermat's Little Theorem when the modulus is NOT prime (P109 cannot handle that case).
Find the count of positive integers up to N that are coprime to N — i.e., GCD(k, N) = 1.
Loop through all prime factors of N up to √N. For each prime factor p found, multiply result by (1 - 1/p), which in integer code is res -= res / p. Then fully divide p out of N. If N > 1 after the loop, N itself is a prime factor.
Prime factors of 12 = {2, 3}. Start res = 12.
Factor 2: res -= res/2 → res = 6. N /= 2 until odd → N = 3.
Factor 3: res -= res/3 → res = 4. N /= 3 → N = 1.
Coprime values ≤12: {1,5,7,11}. Count = 4. Matches formula!int phi(int n) {
int result = n;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
while (n % i == 0) n /= i; // Remove factor completely
result -= result / i; // Apply Euler product term
}
}
if (n > 1) result -= result / n; // n is itself prime
return result;
}Time: O(√N) | Space: O(1). Core primitive in RSA cryptography and modular arithmetic theory.
Count how many numbers between 1 and N are divisible by A, B, or C.
Adding N/A + N/B + N/C double-counts numbers divisible by both A and B. Subtract the pairwise intersections using LCM. But now the triple intersection is under-counted — add N/LCM(A,B,C) back. This is the inclusion-exclusion formula for three sets.
|A ∪ B ∪ C| = |A| + |B| + |C|
- |A∩B| - |B∩C| - |A∩C|
+ |A∩B∩C|long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return (a / gcd(a, b)) * b; }
long long countDivisible(long long n, long long a, long long b, long long c) {
long long count = 0;
count += (n/a) + (n/b) + (n/c); // Primary sets
count -= (n/lcm(a,b)) + (n/lcm(b,c)) + (n/lcm(a,c)); // Pairwise intersections
count += (n / lcm(a, lcm(b, c))); // Triple intersection
return count;
}Time: O(log min(A,B)) | Space: O(1). Always compute LCM as (a / gcd(a,b)) * b — not a * b / gcd — to avoid overflow before the division happens.
Find exactly how many trailing zeros N! has — without computing the factorial itself.
A trailing zero is produced by a factor of 10 = 2 × 5. In any factorial, factors of 2 always outnumber factors of 5. So the trailing zero count equals the total number of times 5 divides into N!. Count contributions from 5, 25, 125, 625, … by summing ⌊N/5^k⌋ until the term reaches zero.
100 / 5 = 20
100 / 25 = 4
100 / 125 = 0
Total trailing zeros = 20 + 4 = 24int trailingZeroes(int n) {
int count = 0;
for (long long i = 5; n / i >= 1; i *= 5)
count += n / i;
return count;
}Time: O(log₅ N) | Space: O(1). Stepping through powers of 5 is dramatically faster than iterating through the factorial.
Find the N-th Catalan number. Direct application: how many valid groupings of N pairs of parentheses exist?
The formula is Cₙ = C(2n, n) / (n+1). Compute C(2n, n) using the incremental nCr function from P99 to avoid factorial overflow. Divide by (n+1) at the end.
long long nCr(int n, int r) {
long long res = 1;
if (r > n - r) r = n - r;
for (int i = 0; i < r; i++) { res *= (n - i); res /= (i + 1); }
return res;
}
long long catalan(int n) {
return nCr(2 * n, n) / (n + 1);
}Time: O(N) | Space: O(1). Catalan numbers grow rapidly — they exceed 64-bit signed integers around N=33. Cap input testing there to prevent overflow.
In how many distinct ways can N identical items be distributed into K distinct bins, with empty bins allowed?
Picture N items as stars (*) and K-1 dividers as bars (|). Distributing 5 items into 3 bins is identical to arranging 5 stars and 2 bars. Total slots = N + K - 1. We choose K-1 of them for the bars. Answer = C(N + K - 1, K - 1).
N = 5, K = 3.
C(5 + 3 - 1, 3 - 1) → C(7, 2) = (7 × 6) / (2 × 1) = 21 wayslong long starsAndBars(int items_n, int bins_k) {
if (items_n == 0 || bins_k == 0) return 1;
return nCr(items_n + bins_k - 1, bins_k - 1);
}Time: O(K) | Space: O(1). Reduces a combinatorial allocation problem to a single nCr call.
Determine whether a point (Px, Py) lies inside or outside an arbitrary N-sided polygon.
Cast an imaginary horizontal ray to the right from the test point. Count how many times it crosses a polygon edge. If the crossing count is odd, the point is inside. If even, it is outside. For each edge, check if the test point's Y falls between the edge vertices' Y values, then compute the X intersection of the ray with that edge.
/ \
| X | ——→ 1 crossing (Odd) = Inside!
\__/
X ————————→ 2 crossings (Even) = Outside!struct Point { double x, y; };
bool isInsidePolygon(vector<Point>& poly, Point test) {
int n = poly.size();
bool inside = false;
for (int i = 0, j = n - 1; i < n; j = i++) {
// Does test.y fall strictly between poly[i].y and poly[j].y?
if ((poly[i].y > test.y) != (poly[j].y > test.y)) {
double intersectX =
(poly[j].x - poly[i].x) * (test.y - poly[i].y) /
(poly[j].y - poly[i].y) + poly[i].x;
if (test.x < intersectX)
inside = !inside; // Toggle on each crossing
}
}
return inside;
}Time: O(N) | Space: O(1). Floating-point precision issues can cause anomalies when the test point lies exactly on a vertex or edge. Add an epsilon guard for production code.
Compute (A × B) mod M safely when both A, B ≈ 10¹⁸ — where standard 64-bit multiplication overflows before the modulo is applied.
Identical in structure to binary exponentiation but using addition instead of multiplication. Decompose B in binary: if the current bit of B is set, add A to the result. Then double A (shift left). This decomposes a single multiplication into O(log B) safe additions that never overflow.
A=5, B=13 (binary: 1101).
B odd → res = (0+5)%10 = 5. A = (5+5)%10 = 0. B = 6.
B even → A = (0+0)%10 = 0. B = 3.
B odd → res = (5+0)%10 = 5. A = (0+0)%10 = 0. B = 1.
B odd → res = (5+0)%10 = 5. Done. 5×13 % 10 = 5long long multiplyFast(long long a, long long b, long long m) {
long long res = 0;
a %= m;
while (b > 0) {
if (b & 1) res = (res + a) % m;
a = (a * 2) % m; // Double A under modulo
b >>= 1;
}
return res;
}Time: O(log B) | Space: O(1). Prevents 10³⁶ intermediate overflow when multiplying two 10¹⁸ values. Use this whenever both operands are close to LLONG_MAX.
Given integers A, B, C, determine whether integer solutions (x, y) exist for the equation Ax + By = C.
By Bézout's identity, the equation Ax + By = C has integer solutions if and only if C is divisible by GCD(A, B). If C % GCD(A, B) ≠ 0, no integer solution exists — regardless of how you choose x and y.
GCD(3, 6) = 3. Does 3 divide 8? 8 % 3 = 2 ≠ 0. No integer solution exists. Example with solution: 3x + 6y = 9. 9 % 3 = 0. Solution exists (e.g., x=3, y=0).
int getGCD(int a, int b) {
return b == 0 ? a : getGCD(b, a % b);
}
bool hasIntegerSolution(int a, int b, int c) {
if (a == 0 && b == 0) return c == 0;
return c % getGCD(abs(a), abs(b)) == 0;
}Time: O(log min(A,B)) | Space: O(1). Use abs() on both inputs — negative values crash standard GCD implementations that expect non-negative inputs.
Given a 2D matrix, answer queries for the sum of any rectangular sub-matrix in O(1) per query after O(R×C) preprocessing.
Build a prefix matrix where prefix[i][j] = sum of all elements in the sub-grid from (0,0) to (i-1, j-1). For a query rectangle (r1,c1) to (r2,c2): take the large rectangle ending at (r2+1, c2+1), subtract the top and left overlaps, then re-add the top-left corner that was subtracted twice.
Sum(r1..r2, c1..c2) = prefix[r2+1][c2+1] - prefix[r1] [c2+1] (remove top strip) - prefix[r2+1][c1] (remove left strip) + prefix[r1] [c1] (restore doubly-removed corner)
class NumMatrix {
vector<vector<int>> prefix;
public:
NumMatrix(vector<vector<int>>& matrix) {
int R = matrix.size(), C = matrix[0].size();
// 1-based indexing to avoid boundary checks
prefix.assign(R + 1, vector<int>(C + 1, 0));
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
prefix[r+1][c+1] = matrix[r][c]
+ prefix[r][c+1]
+ prefix[r+1][c]
- prefix[r][c];
}
int sumRegion(int r1, int c1, int r2, int c2) {
return prefix[r2+1][c2+1]
- prefix[r1] [c2+1]
- prefix[r2+1][c1]
+ prefix[r1] [c1];
}
};Time: O(R×C) precompute, O(1) per query | Space: O(R×C). The optimal architecture for heavily-queried static grids.
Process Q range-update queries on an array where each query adds V to every element in [L, R]. Finalize the array in O(N), not O(Q×N).
Build a diff array. For each query "+V on [L, R]": write diff[L] += V and diff[R+1] -= V. After all queries, run a prefix sum over diff — the running total at each index exactly accumulates all overlapping updates.
Initial diff: [0, 0, 0, 0, 0]
diff[1] += 3, diff[4] -= 3 → [0, 3, 0, 0, -3]
Prefix sum reconstruction:
idx 0: 0
idx 1: 0+3 = 3
idx 2: 3+0 = 3
idx 3: 3+0 = 3
idx 4: 3+(-3) = 0 Bounds accurately respected!vector<int> processUpdates(int n, vector<vector<int>>& updates) {
vector<int> diff(n + 1, 0); // +1 to handle R+1 without overflow
for (auto& u : updates) {
int L = u[0], R = u[1], val = u[2];
diff[L] += val;
diff[R + 1] -= val;
}
vector<int> arr(n);
arr[0] = diff[0];
for (int i = 1; i < n; i++)
arr[i] = arr[i-1] + diff[i];
return arr;
}Time: O(1) per update, O(N) reconstruction | Space: O(N). Completely decouples update frequency from array size — Q updates cost the same as 1 update.
Apply additive offset K across a 2D sub-grid from (r1,c1) to (r2,c2) in O(1) per update. Reconstruct the final matrix in O(R×C).
2D analogue of the 1D difference array. Mark four corners: +K at (r1,c1), -K at (r2+1,c1) and (r1,c2+1), and +K again at (r2+1,c2+1) to neutralize the double-subtraction. Reconstruct with a 2D prefix sweep.
class GridUpdate {
vector<vector<int>> diff;
int R, C;
public:
GridUpdate(int rows, int cols) : R(rows), C(cols) {
diff.assign(R + 2, vector<int>(C + 2, 0)); // +2 padding for corner safety
}
void addRegion(int r1, int c1, int r2, int c2, int val) {
diff[r1] [c1] += val;
diff[r2+1] [c1] -= val;
diff[r1] [c2+1] -= val;
diff[r2+1] [c2+1] += val;
}
vector<vector<int>> build() {
vector<vector<int>> g(R, vector<int>(C, 0));
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++)
g[i][j] = diff[i][j]
+ (i > 0 ? g[i-1][j] : 0)
+ (j > 0 ? g[i][j-1] : 0)
- (i > 0 && j > 0 ? g[i-1][j-1] : 0);
return g;
}
};Time: O(1) update, O(R×C) build | Space: O(R×C). Allocate diff with +2 padding (not +1) — the corner at (r2+1, c2+1) requires both dimensions to have room.
Generate the complete power set (all 2^N subsets) of an array of N unique integers using bit manipulation — no recursion.
An array of size N has exactly 2^N subsets. Iterate a counter i from 0 to 2^N - 1. For each i, the j-th bit being set (i & (1 << j)) != 0 means arr[j] is included in this subset. Each integer from 0 to 2^N-1 uniquely encodes one subset.
vector<vector<int>> generateSubsets(vector<int>& nums) {
int n = nums.size();
int limit = 1 << n; // 2^n subsets
vector<vector<int>> result;
for (int i = 0; i < limit; i++) {
vector<int> subset;
for (int j = 0; j < n; j++)
if (i & (1 << j)) // j-th bit is set in i
subset.push_back(nums[j]);
result.push_back(subset);
}
return result;
}Time: O(N × 2^N) | Space: O(1) auxiliary. Highly optimal for N ≤ 20. Above that, 2^N subsets becomes infeasible to store regardless of method.
Count the number of set bits (1s) in a 32-bit integer, running only as many iterations as there are set bits — not 32.
The expression N & (N-1) clears exactly the lowest-order set bit of N. Repeating this until N reaches zero counts the set bits, and loops only K times where K is the popcount — not 32. This is strictly more efficient than shifting through all 32 bits.
Pass 1: N = 12 & 11 (1100 & 1011) = 1000 (8). Count = 1.
Pass 2: N = 8 & 7 (1000 & 0111) = 0000 (0). Count = 2.
Terminates after exactly 2 iterations (2 set bits). Done.int countSetBits(int n) {
int count = 0;
while (n > 0) {
n &= (n - 1); // Clear the lowest set bit
count++;
}
return count;
}Time: O(K) where K = number of set bits | Space: O(1). Compare with __builtin_popcount(n) which maps to a single CPU instruction on modern hardware — use that in contest code.
Find the two unique elements in an array where every other element appears exactly twice. No auxiliary map allowed — O(1) space only.
XOR the entire array → result = A ^ B (paired duplicates cancel). Extract the rightmost differing bit: diffBit = XOR & -XOR. Use this bit to partition the array into two buckets. A and B end up in different buckets. XOR-ing within each bucket cancels the pairs, leaving A and B isolated.
vector<int> singleNumbers(vector<int>& nums) {
int globalXor = 0;
for (int num : nums) globalXor ^= num;
// Rightmost bit where A and B differ (two's complement trick)
int diffBit = globalXor & -(unsigned int)globalXor;
vector<int> res = {0, 0};
for (int num : nums) {
if ((num & diffBit) == 0) res[0] ^= num; // Bucket A
else res[1] ^= num; // Bucket B
}
return res;
}Time: O(N) | Space: O(1). Cast to unsigned int before the unary negation to prevent undefined behavior on INT_MIN (signed overflow is UB in C++).
Compress a sparse coordinate array where values can reach 10⁹ into a compact index space of size N, preserving relative order.
Copy the array, sort it, deduplicate with std::unique. For each original value, use std::lower_bound to find its rank in the sorted-unique array. This rank (0-indexed or 1-indexed) is its compressed coordinate.
void compressArray(vector<int>& arr) {
vector<int> sorted = arr;
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
for (int i = 0; i < (int)arr.size(); i++) {
// lower_bound gives iterator; subtract begin() for 0-based index; +1 for 1-based
arr[i] = lower_bound(sorted.begin(), sorted.end(), arr[i])
- sorted.begin() + 1;
}
}Time: O(N log N) for sort + N × O(log N) for lower_bound = O(N log N) total | Space: O(N). Prerequisite for segment trees and Fenwick trees on large coordinate spaces.
Given N overlapping intervals, find the maximum number of intervals active simultaneously at any point in time.
Shatter each interval into two events: start (+1) and end (-1). Sort all events by time. Sweep through, maintaining a running count. The maximum running count is the answer. Sorting end events before start events at the same timestamp handles open/closed interval semantics.
int maxOverlaps(vector<vector<int>>& intervals) {
vector<pair<int, int>> events;
for (auto& inv : intervals) {
events.push_back({inv[0], 1}); // Interval starts
events.push_back({inv[1], -1}); // Interval ends
}
sort(events.begin(), events.end()); // Sort by time; ends before starts at ties
int active = 0, maxOverlap = 0;
for (auto& e : events) {
active += e.second;
maxOverlap = max(maxOverlap, active);
}
return maxOverlap;
}Time: O(N log N) | Space: O(N). When a start and end share the same timestamp, the pair sort puts -1 before +1 (since -1 < +1), meaning the ending interval exits before the new one is counted. Adjust if your problem uses closed intervals.
Find the maximum subarray sum in a circular array — the subarray can wrap around from the end back to the beginning.
A circular subarray either does NOT wrap (standard Kadane gives the answer) or it DOES wrap (which means the "excluded" middle segment is the minimum subarray). So: answer = max(maxLinear, totalSum - minLinear). Run both max-Kadane and min-Kadane in a single pass.
int maxSubarraySumCircular(vector<int>& nums) {
int totalSum = 0;
int currMax = 0, maxSum = INT_MIN;
int currMin = 0, minSum = INT_MAX;
for (int x : nums) {
currMax = max(currMax + x, x);
maxSum = max(maxSum, currMax);
currMin = min(currMin + x, x);
minSum = min(minSum, currMin);
totalSum += x;
}
// If all elements are negative, circular wrap gives empty array → discard
if (maxSum < 0) return maxSum;
return max(maxSum, totalSum - minSum);
}Time: O(N) | Space: O(1). The "total minus minimum" inversion is the key insight — it converts the wrap-around problem into a standard linear one.
Find the minimum number of swaps needed to sort an array. Answer in O(N log N).
Compare each element's current position with its target position in the sorted array. Elements that need to swap form directed cycles in a permutation graph. For any cycle of size K, exactly K-1 swaps are needed. Sum (cycle_size - 1) over all cycles.
int minSwaps(vector<int>& nums) {
int n = nums.size();
vector<pair<int, int>> arrPos(n);
for (int i = 0; i < n; i++) arrPos[i] = {nums[i], i};
sort(arrPos.begin(), arrPos.end()); // Sort to find target positions
vector<bool> visited(n, false);
int swaps = 0;
for (int i = 0; i < n; i++) {
if (visited[i] || arrPos[i].second == i) continue;
int cycle_size = 0, j = i;
while (!visited[j]) {
visited[j] = true;
j = arrPos[j].second;
cycle_size++;
}
if (cycle_size > 0) swaps += (cycle_size - 1);
}
return swaps;
}Time: O(N log N) for sort + O(N) for cycle traversal | Space: O(N). The cycle-counting insight is reusable for any "minimum operations to reach target permutation" problem.
Find all elements appearing more than ⌊N/3⌋ times in O(N) time and O(1) space.
At most 2 elements can exceed ⌊N/3⌋ threshold. Maintain two candidate variables with counters. On each element: if it matches a candidate, increment its count. If a counter is zero, adopt this element as a new candidate. Otherwise, decrement both counters (cancellation). A second pass verifies the final candidates.
vector<int> majorityElementII(vector<int>& nums) {
int c1 = 0, c2 = 0, num1 = -1, num2 = -1;
// Phase 1: Find candidate pair via extended voting
for (int el : nums) {
if (el == num1) c1++;
else if (el == num2) c2++;
else if (c1 == 0) { num1 = el; c1 = 1; }
else if (c2 == 0) { num2 = el; c2 = 1; }
else { c1--; c2--; }
}
// Phase 2: Verify candidates against the N/3 threshold
c1 = c2 = 0;
for (int el : nums) {
if (el == num1) c1++;
else if (el == num2) c2++;
}
vector<int> res;
if (c1 > (int)nums.size() / 3) res.push_back(num1);
if (c2 > (int)nums.size() / 3) res.push_back(num2);
return res;
}Time: O(N) | Space: O(1). Generalizes directly: for threshold N/K, maintain K-1 candidates. P77 was the N/2 case with 1 candidate — this is the N/3 case with 2.
Every pattern in this chapter has a one-line mathematical rule. If you can't state it in English before writing code, you don't understand it yet. Go back, derive the rule, then code.
Drill SPF, binary expo, Fermat's inverse, and Euler's totient until they are automatic. These appear verbatim in competitive programming and GATE CSE Algorithms questions.
Prefix sums and difference arrays are the most underrated DSA techniques. Master 1D first, then 2D. Sweep line and coordinate compression unlock segment tree problems.
Move to Codeforces Div3 contests (first 3 problems). Then tackle CSES Problem Set sections: Sorting & Searching, Dynamic Programming, and Graph Algorithms in that order.
P125–P127 are the foundation for an entire category. Add: count bits in a range, single number III variations, and XOR-basis problems to solidify this layer completely.
Never copy code you don't understand. Every line you write should have a reason you can state out loud. Reproduce each problem from memory 24 hours after reading it.
Always write the test case first. Before coding, write 2–3 examples by hand including edge cases (n=0, n=1, all-negative, all-same, sorted/reverse-sorted). Trace your logic on those examples. Code follows naturally. Debugging becomes rare.