Divide & Conquer

Powers of 2 have exactly one set bit. This bit trick is O(1) and appears in many bitmask problems.

n > 0 and (n & (n-1)) == 0

Bit extraction isolates a single bit. Building block for bitmask enumeration.

(n >> i) & 1

Setting a bit turns on a flag. Used in bitmask DP and subset representation.

n | (1 << i)

XOR toggle flips a single bit. Core operation for Hamming distance and bit manipulation.

n ^ (1 << i)

Clearing the lowest set bit is Brian Kernighan's trick for efficient bit counting.

n & (n - 1)

Counting set bits via n &= n-1 runs in O(k) where k is the number of set bits.

count = 0
while n:
    n &= n - 1
    count += 1

Custom key sorting is Python's primary sort mechanism. Foundation for interval and custom-order problems.

a.sort(key=lambda x: x[1])

Multi-key sorting handles tiebreakers. Used in leaderboard and event scheduling.

a.sort(key=lambda x: (x[0], -x[1]))

Counting sort is O(n+k) for bounded integers. Optimal when the range is small.

count = [0] * (max(a) + 1)
for x in a:
    count[x] += 1
result = []
for val, cnt in enumerate(count):
    result.extend([val] * cnt)

Merging sorted lists is the core of merge sort and merge-k-lists.

i = j = 0
merged = []
while i < len(a) and j < len(b):
    if a[i] <= b[j]:
        merged.append(a[i]); i += 1
    else:
        merged.append(b[j]); j += 1
merged.extend(a[i:])
merged.extend(b[j:])

Partition is the heart of quicksort. Same as Lomuto partition — drill until automatic.

def partition(a, lo, hi):
    pivot = a[hi]
    i = lo
    for j in range(lo, hi):
        if a[j] <= pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]
    return i

Euclidean GCD runs in O(log min(a,b)). Foundation for fraction simplification and LCM.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Trial division up to sqrt(n) is the basic primality test. Used in number theory problems.

def is_prime(n):
    if n < 2: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False
    return True

Iterative Fibonacci is O(n) time, O(1) space. Classic DP introduction pattern.

a, b = 0, 1
for _ in range(n):
    a, b = b, a + b
# a is fib(n)

Binary exponentiation computes x^n in O(log n). Essential for modular arithmetic problems.

res = 1
while exp:
    if exp & 1:
        res *= base
    base *= base
    exp >>= 1

Iterative factorial avoids recursion overhead. Used in combinatorics and permutation counting.

res = 1
for i in range(2, n + 1):
    res *= i

Modular arithmetic prevents overflow in combinatorics. pow(a,b,m) is built-in fast mod-exp.

(a * b) % m
pow(a, b, m)  # fast modular exponentiation

Quickselect partitions then recurses into one side. O(n) average for kth element.

def qs(l, r, k):
    p = partition(l, r)
    if p == k: return a[p]
    return qs(p+1, r, k) if p < k else qs(l, p-1, k)

Greedy formula: max count drives idle slots. Total time = max(n_tasks, (max_freq-1)*(n+1) + max_count).

freq = Counter(tasks)
mx = max(freq.values())
mx_cnt = sum(1 for v in freq.values() if v == mx)
return max(len(tasks), (mx - 1) * (n + 1) + mx_cnt)