Math

LeetCode 4098 note: value’s smallest prime factor p decides everything: the next element is at least value + p, then even numbers step by 2; the left side is feasible iff value - p >= 2 * index

GCD, primality tests, the sieve of Eratosthenes / linear sieve / smallest prime factor (SPF), connecting numbers by prime factors with Union-Find, and splitting an array by the last occurrence of prime factors

Combinatorial counting (pairs, ways to split), building the k-th permutation digit by digit, geometry (nearest point, law of cosines, triangle inequality), problems that become formulas after sorting or an observation, plus carry arithmetic, base conversion and fast exponentiation

LeetCode 775 note: turn a counting problem into an existence check and solve it in O(n)

LeetCode 2584 note: coprime products ⇔ no prime factor in both parts; record each prime’s last index, extend reach left to right, and split after i when reach == i

LeetCode 2761 note: sieve primes below n, then try x up to n / 2; when x and n - x are both prime, they form a pair

LeetCode 2523 note: sieve the primes in range, since only adjacent primes can be closest; or trial-divide rightward from left and stop at the first twin primes with gap 2

LeetCode 1998 note: numbers in one component can be permuted freely; union each number with its prime factors via SPF, and the array sorts iff each position’s old and new values share a group

LeetCode 996 note: with n at most 12, use bitmask DP: dp[mask][last] = permutations using the set mask and ending with last; dedupe by using equal values in index order

LeetCode 1354 note: work backwards, since the maximum was set last; jump with a modulo when the gap is large

LeetCode 2963 note: all occurrences of a value must share a part, so last occurrences cut the array into b indivisible blocks; each boundary may be cut or not, giving 2^(b-1)

LeetCode 2376 note: digit DP with state (pos, tight, started, mask); the mask records used digits, and leading zeros must not mark 0 as used