Math & Bit Manipulation

Problem: Compute xⁿ for a float x and an integer n (possibly negative).

Solve it on LeetCode ↗

Constraints: -100.0 < x < 100.0 · -2³¹ ≤ n ≤ 2³¹-1 · n is an integer. · Either x is not zero or n > 0. · -10⁴ ≤ xn ≤ 10⁴

From brute force to the pattern: n multiplications vs log n squarings.

Spot it: Binary exponentiation: xⁿ is the product of x^(2^k) over the set bits of n. Square the base each step.

Why not another pattern? Multiplying n times is O(n) with |n| up to 2³¹.

Approach:

1. If n < 0: x = 1/x, n = −n.
2. While n: if n & 1, result *= x; x *= x; n >>= 1.

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x, n = 1 / x, -n  # x^-n = (1/x)^n
        result = 1.0
        while n:
            if n & 1:
                result *= x  # this power of two is part of n
            x *= x  # x, x^2, x^4, x^8, ...
            n >>= 1
        return result

What the code is doing, line by line:

1. After k squarings, x holds x^(2^k).
2. Each set bit of n multiplies in the matching power.
3. Negative exponents invert the base first.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 0 → 1.
• Negative n.
• n = −2³¹.

Complexity: O(log n) time, O(1) space.

Problem: Exactly two elements appear once; all others twice. Return the two (any order) in O(n) time, O(1) space.

Solve it on LeetCode ↗

Constraints: 2 ≤ nums.length ≤ 3 * 10⁴ · -2³¹ ≤ nums[i] ≤ 2³¹ - 1 · Each integer in nums will appear twice, only two integers will appear once.

From brute force to the pattern: A set or counter is O(n) space; the XOR split is O(1).

Spot it: XOR cancels pairs, leaving a ^ b. Any set bit of it is a bit where a and b differ; split all numbers by that bit and XOR each group separately.

Why not another pattern? A hash set uses O(n) space.

Approach:

1. both = XOR of all.
2. bit = both & −both (lowest set bit).
3. XOR the numbers with that bit set → a; b = both ^ a.

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        both = 0
        for x in nums:
            both ^= x  # pairs cancel: a ^ b remains
        bit = both & -both  # lowest bit where a and b differ
        a = 0
        for x in nums:
            if x & bit:
                a ^= x  # only one of the two singles has this bit
        return [a, both ^ a]

What the code is doing, line by line:

1. x & −x isolates the lowest set bit (two's complement).
2. Each pair lands in the same group and cancels; the singles land in different groups.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Negative numbers.
• Zero as one of the answers.
• Two elements only.

Complexity: O(n) time, O(1) space.

Problem: Count primes strictly less than n.

Solve it on LeetCode ↗

Constraints: 0 ≤ n ≤ 5 * 10⁶

From brute force to the pattern: Trial division: O(n√n). Sieve: O(n log log n).

Spot it: Primality for every number below n → the Sieve of Eratosthenes: each prime crosses out its multiples starting at p².

Why not another pattern? Trial division for each number is O(n√n).

Approach:

1. is_prime = [True] * n; 0 and 1 are not prime.
2. For p up to √n: if prime, mark p², p² + p, … as not prime.
3. Count the remaining Trues.

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        p = 2
        while p * p < n:
            if is_prime[p]:
                is_prime[p * p::p] = [False] * len(range(p * p, n, p))  # cross out multiples
            p += 1
        return sum(is_prime)

What the code is doing, line by line:

1. Multiples below p² were already crossed out by smaller primes.
2. Slice assignment does the crossing out at C speed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n ≤ 2 → 0.
• n = 3 → 1.
• Large n.

Complexity: O(n log log n) time, O(n) space.

Problem: Is n palindromic in every base from 2 to n − 2?

Solve it on LeetCode ↗

Constraints: 4 ≤ n ≤ 10⁵

From brute force to the pattern: Checking every base is O(n log n); the observation is constant time.

Spot it: A math observation: n = 1 · (n − 2) + 2, so in base n − 2 it's "12" for n ≥ 5, not a palindrome. n = 4 is "100" in base 2.

Why not another pattern? Converting to every base works but proves nothing; the answer is always false.

Approach:

1. Return False.

class Solution:
    def isStrictlyPalindromic(self, n: int) -> bool:
        return False  # base n - 2 always gives "12" (for n >= 5); n = 4 is "100" in base 2

What the code is doing, line by line:

1. For n ≥ 5, n − 2 ≥ 3 > 2, so the digits are 1 and 2.
2. The only remaining case, n = 4, fails in base 2.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 4.
• n = 5.
• Large n.

Complexity: O(1).

Problem: Increment elements so that even indices hold primes and odd indices hold non-primes. Return the minimum number of increments.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁵

From brute force to the pattern: Trial division while incrementing is O(n · gap · √M); the sieve makes each index O(1).

Spot it: Each element is independent. A sieve (plus a "next prime at or above x" table) answers even indices; an odd index only needs work if it's prime: x + 1 is non-prime unless x = 2 (3 is prime, so it takes 2 steps to 4).

Why not another pattern? Testing primality by trial division while incrementing is much slower than one sieve.

Approach:

1. Sieve up to a bit above 10⁵ (the next prime after 10⁵ is 100003).
2. next_prime[v] from the top down.
3. Sum per index: even → next_prime[x] − x; odd → 0 if not prime, else 2 if x == 2, else 1.

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        LIMIT = max(nums) + 100  # a prime always appears within 100 above any value <= 10^5
        is_prime = [True] * (LIMIT + 1)
        is_prime[0] = is_prime[1] = False
        p = 2
        while p * p <= LIMIT:
            if is_prime[p]:
                is_prime[p * p::p] = [False] * len(range(p * p, LIMIT + 1, p))
            p += 1
        next_prime = [0] * (LIMIT + 2)
        nxt = LIMIT + 1
        for v in range(LIMIT, -1, -1):
            if is_prime[v]:
                nxt = v
            next_prime[v] = nxt  # smallest prime >= v
        ops = 0
        for i, x in enumerate(nums):
            if i % 2 == 0:
                ops += next_prime[x] - x  # climb to a prime
            elif is_prime[x]:
                ops += 2 if x == 2 else 1  # x + 1 is even and > 2, except 2 + 1 = 3
        return ops

What the code is doing, line by line:

1. Increments only go up, so an even index needs the nearest prime at or above it.
2. For an odd prime x > 2, x + 1 is even and greater than 2, hence composite.
3. Prime gaps below 10⁵ are under 100, so the sieve limit is safe.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Value 1 at an even index (next prime 2).
• Value 2 at an odd index (needs 2 steps).
• Already alternating → 0.

Complexity: O(M log log M + n) time, O(M) space.

Problem: Reverse the digits of a 32-bit signed integer; return 0 if the result overflows.

Solve it on LeetCode ↗

Constraints: -2³¹ ≤ x ≤ 2³¹ - 1

From brute force to the pattern: String reversal is fine in Python; the digit loop is what C++/Java need.

Spot it: Digit arithmetic: x % 10 takes the last digit, x // 10 drops it, rev · 10 + d appends it. Work with |x| and restore the sign.

Why not another pattern? String reversal works in Python but hides the overflow reasoning interviewers ask about.

Approach:

1. sign, x = |x|.
2. While x: rev = rev · 10 + x % 10, x //= 10.
3. Apply the sign; return 0 outside [−2³¹, 2³¹ − 1].

class Solution:
    def reverse(self, x: int) -> int:
        sign = -1 if x < 0 else 1
        x = abs(x)
        rev = 0
        while x:
            rev = rev * 10 + x % 10  # move the last digit of x to the end of rev
            x //= 10
        rev *= sign
        return rev if -2**31 <= rev <= 2**31 - 1 else 0

What the code is doing, line by line:

1. Working with abs(x) avoids Python's floor-division surprises with negatives.
2. In a 32-bit language, check rev > (2³¹ − 1) // 10 before multiplying.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Negative numbers.
• Trailing zeros (120 → 21).
• Overflow (1534236469 → 0).

Complexity: O(log x) time, O(1) space.

Problem: Divide without *, / or %, truncating toward zero; clamp to the 32-bit range.

Solve it on LeetCode ↗

Constraints: -2³¹ ≤ dividend, divisor ≤ 2³¹ - 1 · divisor != 0

From brute force to the pattern: Subtracting one divisor at a time is O(quotient); shifting is O(32).

Spot it: Long division in binary: bit shifts double the divisor. From the largest divisor << k that fits, subtract and add 1 << k — each bit of the quotient decided once.

Why not another pattern? Repeated subtraction is O(quotient), up to 2³¹ steps.

Approach:

1. Handle the sign; work with absolute values.
2. For k from 31 down to 0: if (b << k) ≤ a: a −= b << k, q += 1 << k.
3. Apply the sign and clamp.

class Solution:
    def divide(self, dividend: int, divisor: int) -> int:
        negative = (dividend < 0) != (divisor < 0)
        a, b = abs(dividend), abs(divisor)
        q = 0
        for k in range(31, -1, -1):
            if (b << k) <= a:  # divisor * 2^k still fits
                a -= b << k
                q += 1 << k  # this bit of the quotient is 1
        q = -q if negative else q
        return max(-2**31, min(2**31 - 1, q))  # only -2^31 / -1 overflows

What the code is doing, line by line:

1. Trying shifts from large to small decides the quotient's bits from the top, like long division.
2. Truncation toward zero comes from working with absolute values.
3. The only overflow case is −2³¹ / −1.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• −2³¹ / −1 → clamp.
• Negative operands.
• Divisor larger than the dividend → 0.

Complexity: O(32) time, O(1) space.

Problem: Every element appears three times except one, which appears once. Find it in O(n) time and O(1) space.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 3 * 10⁴ · -2³¹ ≤ nums[i] ≤ 2³¹ - 1 · Each element in nums appears exactly three times except for one element which appears once.

From brute force to the pattern: A counter uses O(n) space; per-bit counting uses O(1).

Spot it: For each bit position, the triple elements contribute a multiple of 3 ones. So (count of ones) % 3 is exactly the single number's bit there.

Why not another pattern? A hash map works but uses O(n) space; XOR only cancels pairs, not triples.

Approach:

1. For each of the 32 bits: count numbers with that bit set; if count % 3, set the bit in the answer.
2. Fix the sign for negative numbers (bit 31).

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for b in range(32):
            ones = sum((x >> b) & 1 for x in nums)  # how many numbers have bit b set
            if ones % 3:
                result |= 1 << b  # tripled numbers contribute multiples of 3
        if result >= 2**31:
            result -= 2**32  # bit 31 set: it's a negative number in 32-bit
        return result

What the code is doing, line by line:

1. Python's >> on negatives sign-extends, and & 1 reads the two's-complement bit correctly.
2. The final adjustment converts the 32-bit pattern back to a signed integer.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Negative single number.
• Zero as the single number.
• One element.

Complexity: O(32 · n) time, O(1) space.

Problem: Return the number of trailing zeros in n!.

Solve it on LeetCode ↗

Constraints: 0 ≤ n ≤ 10⁴

From brute force to the pattern: Computing n! is O(n) big multiplications; counting 5s is O(log n).

Spot it: Each trailing zero needs a factor 10 = 2 · 5, and 2s are plentiful, so count the 5s in 1..n (multiples of 25 give two, …).

Why not another pattern? Computing n! is huge; counting zeros of the number is wasteful.

Approach:

1. zeros = 0; while n: n //= 5; zeros += n.

class Solution:
    def trailingZeroes(self, n: int) -> int:
        zeros = 0
        while n:
            n //= 5
            zeros += n  # multiples of 5, then of 25, 125, ...
        return zeros

What the code is doing, line by line:

1. n // 5 counts multiples of 5; dividing again counts multiples of 25 (an extra 5 each), and so on.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n < 5 → 0.
• n = 25 → 6.
• Large n.

Complexity: O(log₅ n) time, O(1) space.

Problem: Return the total area covered by two axis-aligned rectangles.

Solve it on LeetCode ↗

Constraints: -10⁴ ≤ ax1 ≤ ax2 ≤ 10⁴ · -10⁴ ≤ ay1 ≤ ay2 ≤ 10⁴ · -10⁴ ≤ bx1 ≤ bx2 ≤ 10⁴ · -10⁴ ≤ by1 ≤ by2 ≤ 10⁴

From brute force to the pattern: Grid counting is infeasible; inclusion–exclusion is constant time.

Spot it: Inclusion–exclusion: add both areas, subtract the intersection. The intersection's sides come from min of right edges and max of left edges.

Why not another pattern? Counting unit squares is impossible for coordinates up to 10⁴.

Approach:

1. w = max(0, min(ax2, bx2) − max(ax1, bx1)), same for height.
2. Return areaA + areaB − w · h.

class Solution:
    def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:
        overlap_w = max(0, min(ax2, bx2) - max(ax1, bx1))  # 0 if they don't overlap horizontally
        overlap_h = max(0, min(ay2, by2) - max(ay1, by1))
        area_a = (ax2 - ax1) * (ay2 - ay1)
        area_b = (bx2 - bx1) * (by2 - by1)
        return area_a + area_b - overlap_w * overlap_h  # don't count the shared part twice

What the code is doing, line by line:

1. The overlap is itself a rectangle, bounded by the inner edges.
2. A negative width means no overlap; max(0, …) handles it.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No overlap.
• One inside the other.
• Touching edges (overlap 0).

Complexity: O(1).

Problem: n bulbs start off; on round i every i-th bulb toggles. How many are on after n rounds?

Solve it on LeetCode ↗

Constraints: 0 ≤ n ≤ 10⁹

From brute force to the pattern: Simulation is far too slow; the divisor-parity argument gives a formula.

Spot it: Bulb k is toggled once for each divisor of k. Divisors pair up (d, k/d) except for perfect squares → only perfect squares end up on.

Why not another pattern? Simulating is O(n log n) with n up to 10⁹.

Approach:

1. Return isqrt(n).

from math import isqrt

class Solution:
    def bulbSwitch(self, n: int) -> int:
        return isqrt(n)  # 1, 4, 9, ... have an odd number of divisors

What the code is doing, line by line:

1. An odd number of toggles leaves a bulb on.
2. isqrt counts the perfect squares ≤ n exactly (no float rounding).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 0 → 0.
• Perfect square n.
• Large n.

Complexity: O(log n) time, O(1) space.

Problem: Add two integers without using + or −.

Solve it on LeetCode ↗

Constraints: -1000 ≤ a, b ≤ 1000

From brute force to the pattern: Bit-by-bit addition with an explicit carry loop is the same idea, one bit at a time.

Spot it: Bitwise addition: a ^ b is the sum ignoring carries, (a & b) << 1 is the carries. Repeat until no carry. In Python, mask to 32 bits to emulate fixed-width integers.

Why not another pattern? sum([a, b]) sidesteps the point; the question is about the binary adder.

Approach:

1. mask = 0xFFFFFFFF.
2. While b: a, b = (a ^ b) & mask, ((a & b) << 1) & mask.
3. Convert back: if a > 0x7FFFFFFF, it's negative: ~(a ^ mask).

class Solution:
    def getSum(self, a: int, b: int) -> int:
        mask = 0xFFFFFFFF  # emulate 32-bit integers
        a &= mask
        b &= mask
        while b:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask  # sum without carry, then the carry
        return a if a <= 0x7FFFFFFF else ~(a ^ mask)  # back to a signed value

What the code is doing, line by line:

1. Each round moves the carries one position left; they disappear after at most 32 rounds.
2. ~(a ^ mask) turns a 32-bit two's-complement pattern into Python's negative integer.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Negative numbers.
• a = −b (result 0).
• Zero.

Complexity: O(32) time, O(1) space.

Problem: Compute a^b mod 1337 where b is a huge number given as a digit array.

Solve it on LeetCode ↗

Constraints: 1 ≤ a ≤ 2³¹ - 1 · 1 ≤ b.length ≤ 2000 · 0 ≤ b[i] ≤ 9 · b does not contain leading zeros.

From brute force to the pattern: Converting b to an integer creates a 2000-digit number; the digit recurrence never does.

Spot it: Modular exponentiation digit by digit: appending digit d to the exponent turns r = a^x into r^10 · a^d (mod 1337).

Why not another pattern? Building b as an integer and calling pow works in Python, but the digit recurrence is the intended idea.

Approach:

1. result = 1.
2. For each digit d: result = pow(result, 10, 1337) · pow(a, d, 1337) % 1337.

class Solution:
    def superPow(self, a: int, b: List[int]) -> int:
        MOD = 1337
        result = 1
        for d in b:
            result = pow(result, 10, MOD) * pow(a, d, MOD) % MOD  # exponent x -> 10x + d
        return result

What the code is doing, line by line:

1. If the exponent so far is x, appending d makes it 10x + d.
2. a^(10x + d) = (a^x)^10 · a^d, all reducible mod 1337.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• a multiple of 1337 → 0.
• b = [0] style exponents.
• Large a.

Complexity: O(len(b) · log 10) time, O(1) space.

Problem: Step i moves i units left or right. Return the fewest steps to land exactly on target.

Solve it on LeetCode ↗

Constraints: -10⁹ ≤ target ≤ 10⁹ · target != 0

From brute force to the pattern: BFS on positions grows exponentially; the parity argument is O(√t).

Spot it: By symmetry use |target|. Take steps 1, 2, …, k all to the right until the sum reaches the target. Flipping step j subtracts 2j, so we need sum − target to be even — a parity argument.

Why not another pattern? BFS over positions explodes.

Approach:

1. t = |target|, k = 0, s = 0.
2. While s < t or (s − t) is odd: k += 1, s += k.
3. Return k.

class Solution:
    def reachNumber(self, target: int) -> int:
        t = abs(target)  # left and right are symmetric
        k = 0
        s = 0
        while s < t or (s - t) % 2:
            k += 1
            s += k  # take one more step to the right
        return k  # flip steps worth (s - t) / 2 to land exactly

What the code is doing, line by line:

1. Flipping a set of steps that sums to (s − t)/2 reduces the total by exactly s − t; any even surplus can be fixed.
2. An odd surplus can't be fixed by flips, so another step is needed.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Negative target.
• Target reached exactly by 1 + 2 + … + k.
• Target needing two extra steps.

Complexity: O(√|target|) time, O(1) space.

Problem: Find the secret 6-letter word with Master.guess(word) (returns exact-position matches) within the allowed guesses.

Solve it on LeetCode ↗

Constraints: 1 ≤ words.length ≤ 100 · words[i].length == 6 · words[i] consist of lowercase English letters. · All the strings of words are unique. · secret exists in words. · 10 ≤ allowedGuesses ≤ 30

From brute force to the pattern: Guessing words one by one can take 100 guesses; the minimax filter needs about 10.

Spot it: Each guess partitions the candidates by match count; only the group matching the reply survives. Choosing the guess whose largest group is smallest (minimax) shrinks the candidates fastest. It's a counting/combinatorics game rather than a data-structure problem.

Why not another pattern? Random guesses usually work but can fail the strict tests; guessing in order fails easily.

Approach:

1. matches(a, b) = positions where letters agree.
2. Pick the candidate whose worst-case group (over match counts with all other candidates) is smallest.
3. Guess it; if 6, done. Otherwise keep candidates with exactly the same match count to the guess.

from collections import Counter

class Solution:
    def findSecretWord(self, words: List[str], master: "Master") -> None:
        def matches(a, b):
            return sum(x == y for x, y in zip(a, b))

        candidates = words[:]
        while candidates:
            guess = min(candidates, key=lambda w: max(Counter(matches(w, o) for o in candidates).values()))  # minimax
            hit = master.guess(guess)
            if hit == 6:
                return
            candidates = [w for w in candidates if matches(w, guess) == hit]  # only words consistent with the reply

What the code is doing, line by line:

1. The secret has exactly hit matches with the guess, so any word that doesn't is eliminated.
2. Minimising the largest group guarantees the most progress in the worst case.
3. With 100 words, each round costs O(n²) comparisons.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Two candidates.
• Words sharing many letters.
• The first guess is the secret.

Complexity: O(n² · 6) per guess, at most about 10 guesses.

Problem: Return the smallest prime palindrome ≥ n.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁸

From brute force to the pattern: Scanning upward from n and checking each number takes too long near 10⁷; generating palindromes skips almost everything.

Spot it: Every even-length palindrome is divisible by 11, so only 11 and odd-length palindromes matter. Build them from a root (left half) in increasing order and test primality with trial division up to √x.

Why not another pattern? Testing every number upward hits the 10⁷–10⁸ gap with no 8-digit prime palindromes: too slow.

Approach:

1. If 8 ≤ n ≤ 11, return 11.
2. For roots 1, 2, 3, …: x = int(root + reverse(root without its last digit)).
3. Return the first x ≥ n that is prime.

class Solution:
    def primePalindrome(self, n: int) -> int:
        def is_prime(x):
            if x < 2:
                return False
            d = 2
            while d * d <= x:
                if x % d == 0:
                    return False
                d += 1
            return True

        if 8 <= n <= 11:
            return 11  # the only even-length prime palindrome
        root = 1
        while True:
            s = str(root)
            x = int(s + s[-2::-1])  # odd-length palindrome: 123 -> 12321
            if x >= n and is_prime(x):
                return x
            root += 1

What the code is doing, line by line:

1. s[-2::-1] mirrors the root without repeating its last digit, giving odd length.
2. Roots in increasing order produce odd-length palindromes in increasing order.
3. Even-length palindromes are multiples of 11 (alternating digit sum is 0), so only 11 itself can be prime.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 2.
• n between 8 and 11 → 11.
• Large n (answer 100030001).

Complexity: About O(√answer) per primality test over roughly 10⁴ roots.

Problem: Return the minimum bit flips in a and b so that a | b == c.

Solve it on LeetCode ↗

Constraints: 1 ≤ a ≤ 10^9 · 1 ≤ b ≤ 10^9 · 1 ≤ c ≤ 10^9

From brute force to the pattern: Trying flip sets is exponential; bit-by-bit is O(31).

Spot it: Bits are independent → examine each bit position: c-bit 1 needs at least one 1; c-bit 0 needs both 0.

Why not another pattern? Trying flip combinations is exponential in the number of bits.

Approach:

1. While any of a, b, c is non-zero: look at their lowest bits.
2. c-bit 1: +1 if both a-bit and b-bit are 0. c-bit 0: + a-bit + b-bit.
3. Shift all right.

class Solution:
    def minFlips(self, a: int, b: int, c: int) -> int:
        flips = 0
        while a or b or c:
            x, y, z = a & 1, b & 1, c & 1
            if z:
                flips += 1 if x == 0 and y == 0 else 0  # need at least one 1
            else:
                flips += x + y  # both must become 0
            a >>= 1
            b >>= 1
            c >>= 1
        return flips

What the code is doing, line by line:

1. OR works bit by bit, so each position is solved independently.
2. Turning one 0 into 1 suffices when c needs a 1; when c needs 0, every 1 must go.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already equal → 0.
• c = 0 (clear all bits).
• Both a and b have a 1 where c has 0 (two flips).

Complexity: O(log max(a, b, c)) time, O(1) space.

Problem: Return the smaller angle (degrees) between the hour and minute hands at hour:minutes.

Solve it on LeetCode ↗

Constraints: 1 ≤ hour ≤ 12 · 0 ≤ minutes ≤ 59

From brute force to the pattern: Constant time either way; precision of the formulas is the point.

Spot it: Clock arithmetic: compute each hand's angle from 12 o'clock, take the difference and its complement to 360.

Why not another pattern? Forgetting that the hour hand moves during the hour is the common mistake.

Approach:

1. minute_angle = 6 · minutes.
2. hour_angle = 30 · (hour % 12) + 0.5 · minutes.
3. d = |h − m|; return min(d, 360 − d).

class Solution:
    def angleClock(self, hour: int, minutes: int) -> float:
        minute_angle = 6 * minutes  # 360 / 60
        hour_angle = 30 * (hour % 12) + 0.5 * minutes  # also moves while the minutes pass
        d = abs(hour_angle - minute_angle)
        return min(d, 360 - d)  # the smaller of the two angles

What the code is doing, line by line:

1. hour % 12 maps 12 to 0.
2. The hour hand moves 30° per 60 minutes = 0.5° per minute.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• 12:00 → 0.
• Hands overlapping mid-hour.
• Angle > 180 (take 360 − d).

Complexity: O(1).

Problem: Return the k-th smallest divisor of n, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ n ≤ 1000

From brute force to the pattern: Scanning 1..n is O(n); the paired scan is O(√n).

Spot it: Divisors pair up around √n: collect d ≤ √n in order, their partners n/d come in reverse order → O(√n).

Why not another pattern? Checking all 1..n is O(n) (fine for 1000, but the √n idea is what's asked).

Approach:

1. small = [d for d ≤ √n if n % d == 0].
2. large = [n // d for d in reversed(small) if d * d != n].
3. Return the k-th of small + large, or −1.

class Solution:
    def kthFactor(self, n: int, k: int) -> int:
        small = []
        d = 1
        while d * d <= n:
            if n % d == 0:
                small.append(d)
            d += 1
        large = [n // d for d in reversed(small) if d * d != n]  # partners, increasing
        divisors = small + large
        return divisors[k - 1] if k <= len(divisors) else -1

What the code is doing, line by line:

1. Each d ≤ √n that divides n has a partner n/d ≥ √n.
2. A perfect square's root is its own partner, so it's not repeated.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k larger than the divisor count → −1.
• Perfect squares.
• n prime.

Complexity: O(√n) time, O(√n) space for the divisors.

Problem: Concatenate the binary forms of 1..n; return the value mod 10⁹ + 7.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁵

From brute force to the pattern: String building is O(n log n) and needs big-integer conversion; shifting with mod is O(n).

Spot it: Appending i's bits means value = (value << bits(i)) | i. The bit length grows by one at each power of two (bit manipulation).

Why not another pattern? Building the binary string is O(n log n) characters and a huge number.

Approach:

1. bits = 0; for i in 1..n: if i is a power of two (i & (i − 1) == 0), bits += 1.
2. value = ((value << bits) | i) % MOD.

class Solution:
    def concatenatedBinary(self, n: int) -> int:
        MOD = 10**9 + 7
        value = 0
        bits = 0
        for i in range(1, n + 1):
            if i & (i - 1) == 0:
                bits += 1  # a power of two: one more binary digit
            value = ((value << bits) | i) % MOD  # append i's binary digits
        return value

What the code is doing, line by line:

1. i & (i − 1) == 0 is true exactly for powers of two.
2. Shifting left by bits makes room for i, and OR writes it in.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 1.
• Powers of two.
• Large n (mod).

Complexity: O(n) time, O(1) space.

Problem: Count digit strings of length n (up to 10¹⁵) with even digits at even indices and prime digits at odd indices (mod 10⁹ + 7).

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10¹⁵

From brute force to the pattern: n multiplications vs log n.

Spot it: Positions are independent: multiply choices. With n up to 10¹⁵, use fast modular exponentiation.

Why not another pattern? Multiplying one position at a time is O(n).

Approach:

1. even = (n + 1) // 2, odd = n // 2.
2. Return pow(5, even, MOD) · pow(4, odd, MOD) % MOD.

class Solution:
    def countGoodNumbers(self, n: int) -> int:
        MOD = 10**9 + 7
        even_slots = (n + 1) // 2  # indices 0, 2, 4, ...: digits 0, 2, 4, 6, 8
        odd_slots = n // 2  # indices 1, 3, 5, ...: digits 2, 3, 5, 7
        return pow(5, even_slots, MOD) * pow(4, odd_slots, MOD) % MOD

What the code is doing, line by line:

1. Each even index has 5 choices and each odd index 4, independently.
2. Python's three-argument pow does binary exponentiation mod MOD.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 5.
• Huge n.
• n = 4 → 400.

Complexity: O(log n) time, O(1) space.

Problem: Sort the GCDs of all pairs; answer queries for the value at given indices.

Solve it on LeetCode ↗

Constraints: 2 ≤ n == nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 5 * 10⁴ · 1 ≤ queries.length ≤ 10⁵ · 0 ≤ queries[i] < n * (n - 1) / 2

From brute force to the pattern: All pairs: O(n²). Counting by multiples: O(M log M).

Spot it: There are up to 5·10⁹ pairs, so count them by value. Pairs whose gcd is a multiple of g are C(m_g, 2) where m_g counts multiples of g. Subtract the counts for 2g, 3g, … (inclusion–exclusion from the top). Then prefix sums over g and a binary search per query.

Why not another pattern? Computing all pair GCDs is O(n²).

Approach:

1. freq[v] = occurrences of v; m_g = Σ freq[g · t].
2. From g = max down to 1: exact[g] = C(m_g, 2) − Σ exact[t · g] for t ≥ 2.
3. prefix[g] = pairs with gcd ≤ g; answer q by bisect_right(prefix, q).

from bisect import bisect_right
from itertools import accumulate

class Solution:
    def gcdValues(self, nums: List[int], queries: List[int]) -> List[int]:
        top = max(nums)
        freq = [0] * (top + 1)
        for x in nums:
            freq[x] += 1
        exact = [0] * (top + 1)  # pairs whose gcd is exactly g
        for g in range(top, 0, -1):
            m = sum(freq[g::g])  # numbers divisible by g
            exact[g] = m * (m - 1) // 2 - sum(exact[2 * g::g])  # remove pairs with a larger gcd
        prefix = list(accumulate(exact))  # prefix[g]: pairs with gcd <= g
        return [bisect_right(prefix, q) for q in queries]  # first g whose prefix exceeds q

What the code is doing, line by line:

1. Both numbers of a pair are multiples of g exactly when g divides their gcd.
2. Going from large g to small, the counts for multiples of g are already exact, so subtracting them leaves gcd exactly g.
3. prefix[g] counts pairs at sorted positions 0..prefix[g] − 1; the answer for index q is the first g with prefix[g] > q.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Repeated values.
• All values coprime (every gcd is 1).
• Two elements.

Complexity: O(M log M + q log M) time (harmonic sums over M = max(nums)), O(M) space.

Problem: nums is a permutation of 1..n. Count distinct values of nums[i] ^ nums[j] ^ nums[k] with i ≤ j ≤ k.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ n · nums is a permutation of integers from 1 to n.

From brute force to the pattern: Triple loop: O(n³); the observation is constant time.

Spot it: A bit-manipulation observation: indices may repeat, so any single value x = x ^ y ^ y is reachable, and with 1..n available every number below 2^(bit length of n) can be formed for n ≥ 3. For n ≤ 2, the answer is n.

Why not another pattern? All triples are O(n³); even pairs-plus-one is O(n²).

Approach:

1. If n ≤ 2, return n.
2. Otherwise return 1 << n.bit_length().

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2:
            return n  # n = 1: {1}; n = 2: {1, 2}
        return 1 << n.bit_length()  # every value from 0 to 2^bits - 1 is reachable

What the code is doing, line by line:

1. XOR never sets a bit above the highest bit of n, so values stay below 2^bits.
2. With 1, 2, 3 and the top power of two available, every combination below 2^bits is reachable (0 = 1 ^ 2 ^ 3).
3. For n ≤ 2 there aren't enough values to reach the rest.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 1.
• n = 2 → 2.
• n a power of two.

Complexity: O(1) time and space.

Problem: Return the length of the longest subsequence whose XOR is non-zero (0 if none).

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ 10⁹

From brute force to the pattern: Checking subsequences is exponential; three cases cover everything.

Spot it: XOR reasoning: if the whole array's XOR is non-zero, take everything. If it's zero, removing any non-zero element x leaves XOR x ≠ 0. Only an all-zero array has no answer.

Why not another pattern? Subsequence DP over XOR values is far too big.

Approach:

1. total = XOR of all.
2. total ≠ 0 → n; all zeros → 0; else n − 1.

from functools import reduce
from operator import xor

class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        if reduce(xor, nums) != 0:
            return len(nums)  # the whole array works
        if not any(nums):
            return 0  # every subsequence XORs to 0
        return len(nums) - 1  # removing one non-zero x leaves XOR x

What the code is doing, line by line:

1. XOR of everything except x equals total ^ x = x when total = 0.
2. A subsequence of only zeros always XORs to 0.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All zeros → 0.
• One non-zero element.
• Total XOR is zero.

Complexity: O(n) time, O(1) space.

Problem: n friends in a circle; repeatedly count k and remove that friend. Return the winner (1-indexed).

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ n ≤ 500

From brute force to the pattern: List simulation is O(n²); the recurrence is O(n).

Spot it: The Josephus problem. After the first removal the game restarts with n − 1 people, shifted by k, so the winner's position follows the recurrence J(i) = (J(i − 1) + k) mod i.

Why not another pattern? Simulating with a list is O(n²) (or O(nk) with a queue).

Approach:

1. pos = 0 (with one person, the winner is at index 0).
2. For i from 2 to n: pos = (pos + k) % i.
3. Return pos + 1.

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        pos = 0  # winner's 0-based position with 1 person
        for i in range(2, n + 1):
            pos = (pos + k) % i  # adding a person shifts everyone by k
        return pos + 1

What the code is doing, line by line:

1. With i people, removing the k-th leaves i − 1 people starting just after it, i.e. everyone's position shifted by k.
2. Undoing that shift from 1 person up to n gives the winner's original seat.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 → n.
• n = 1 → 1.
• k larger than n.

Complexity: O(n) time, O(1) space.

Problem: Return the maximum len(a) · len(b) over pairs of words with no common letters.

Solve it on LeetCode ↗

Constraints: 2 ≤ words.length ≤ 1000 · 1 ≤ words[i].length ≤ 1000 · words[i] consists only of lowercase English letters.

From brute force to the pattern: Pairwise string checks are O(n² L); masks make each check O(1).

Spot it: Represent each word's letters as a bitmask; "no common letters" becomes mask_a & mask_b == 0, an O(1) check.

Why not another pattern? Comparing letter sets pairwise as strings is O(n² · L).

Approach:

1. Mask per word (keep the longest word per mask).
2. For every pair of masks with a & b == 0, update the product.

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        longest = {}  # letter mask -> longest word length with exactly those letters
        for w in words:
            mask = 0
            for ch in w:
                mask |= 1 << (ord(ch) - 97)
            longest[mask] = max(longest.get(mask, 0), len(w))
        best = 0
        items = list(longest.items())
        for i, (m1, l1) in enumerate(items):
            for m2, l2 in items[i + 1:]:
                if m1 & m2 == 0:
                    best = max(best, l1 * l2)  # no shared letters
        return best

What the code is doing, line by line:

1. Words with the same letter set only need their longest representative.
2. A bitwise AND is zero exactly when no letter is shared.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No valid pair → 0.
• Words with repeated letters.
• Many words with the same letters.

Complexity: O(Σ L + m²) time for m distinct masks, O(m) space.

Problem: Count distinct values of nums[i] ^ nums[j] ^ nums[k] with i ≤ j ≤ k.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 1500 · 1 ≤ nums[i] ≤ 1500

From brute force to the pattern: Triple loops: O(n³); two set steps: O(V²).

Spot it: XORs of values ≤ 1500 stay below 2048, so sets of results are tiny. Build the set of pair XORs (i ≤ j, so x ^ x = 0 is included), then XOR each with every value — bit manipulation with small sets instead of triple loops over indices.

Why not another pattern? Triple loops over 1500 elements are 5·10⁸.

Approach:

1. vals = set(nums).
2. pairs = {a ^ b for a, b in vals} (including a = b).
3. triples = {p ^ c for p in pairs for c in vals}; return its size.

class Solution:
    def uniqueXorTriplets(self, nums: List[int]) -> int:
        vals = set(nums)
        pairs = {a ^ b for a in vals for b in vals}  # i <= j allows a == b (giving 0)
        triples = {p ^ c for p in pairs for c in vals}  # add the third element
        return len(triples)

What the code is doing, line by line:

1. Only distinct values matter, and indices may repeat, so pairs of values (including equal ones) cover all i ≤ j.
2. Both sets have at most 2048 elements, so the final step is about 3 million operations.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One element → 1.
• Duplicates.
• Values that are powers of two.

Complexity: O(V² + 2048 · V) time for V distinct values, O(2048) space.

Problem: Swaps are allowed only between values whose AND equals k. Return the largest k that lets you sort the permutation.

Solve it on LeetCode ↗

Constraints: 1 ≤ n == nums.length ≤ 10⁵ · 0 ≤ nums[i] ≤ n - 1 · nums is a permutation of integers from 0 to n - 1.

From brute force to the pattern: Testing each k by building swap graphs is slow; the AND of misplaced values is O(n).

Spot it: Every misplaced value must take part in a swap, and a swap's AND keeps only bits shared by both values, so k can't have a bit missing from any misplaced value: k ≤ AND of misplaced values. That bound is always achievable, so the answer is a one-line bit-manipulation formula.

Why not another pattern? Trying every k with a graph check is O(n²) or worse.

Approach:

1. AND together every nums[i] with nums[i] != i.
2. Return it (0 if nothing is misplaced).

from functools import reduce
from operator import and_

class Solution:
    def sortPermutation(self, nums: List[int]) -> int:
        misplaced = [x for i, x in enumerate(nums) if x != i]
        return reduce(and_, misplaced) if misplaced else 0  # bits every moved value shares

What the code is doing, line by line:

1. A value that must move is swapped at least once, so every bit of k is in that value.
2. With k equal to the common bits of all misplaced values, they can be sorted (checked against brute force on small cases).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Already sorted → 0.
• Two values swapped.
• Misplaced values with no common bits → 0.

Complexity: O(n) time, O(1) space.

Problem: Return the largest area of a square that fits inside the intersection of at least two of the axis-aligned rectangles.

Solve it on LeetCode ↗

Constraints: n == bottomLeft.length == topRight.length · 2 ≤ n ≤ 10³ · bottomLeft[i].length == topRight[i].length == 2 · 1 ≤ bottomLeft[i][0], bottomLeft[i][1] ≤ 10⁷ · 1 ≤ topRight[i][0], topRight[i][1] ≤ 10⁷ · bottomLeft[i][0] < topRight[i][0] · bottomLeft[i][1] < topRight[i][1]

From brute force to the pattern: All pairs is already the intended O(n²) solution.

Spot it: Geometry: the intersection of two axis-aligned rectangles is a rectangle with width min(right) − max(left), height likewise. Its largest square has side min(w, h).

Why not another pattern? Grids or sweeps are unnecessary; with n ≤ 1000, checking all pairs is fast.

Approach:

1. For every pair: w = min(c) − max(a), h = min(d) − max(b).
2. side = min(w, h); keep the largest positive side.
3. Return side².

class Solution:
    def largestSquareArea(self, bottomLeft: List[List[int]], topRight: List[List[int]]) -> int:
        n = len(bottomLeft)
        best = 0
        for i in range(n):
            for j in range(i + 1, n):
                w = min(topRight[i][0], topRight[j][0]) - max(bottomLeft[i][0], bottomLeft[j][0])
                h = min(topRight[i][1], topRight[j][1]) - max(bottomLeft[i][1], bottomLeft[j][1])
                best = max(best, min(w, h))  # negative when they don't overlap
        return best * best

What the code is doing, line by line:

1. Overlap in each axis is "smaller right edge minus larger left edge".
2. Intersections of more rectangles are smaller, so pairs are enough.
3. A non-positive side means no square.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No overlaps → 0.
• Touching edges (side 0).
• One rectangle inside another.

Complexity: O(n²) time, O(1) space.

Problem: A sensor covers cells within Chebyshev distance k. Return the fewest sensors that cover an n × m grid.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10³ · 1 ≤ m ≤ 10³ · 0 ≤ k ≤ 10³

From brute force to the pattern: Greedy placement gives the same answer slowly; the formula is constant time.

Spot it: Chebyshev distance k is a (2k + 1)-wide square, and rows and columns are independent → tile each dimension: a math formula.

Why not another pattern? Placing sensors greedily cell by cell gives the same count but more work.

Approach:

1. side = 2k + 1.
2. Return ceil(n / side) · ceil(m / side).

class Solution:
    def minSensors(self, n: int, m: int, k: int) -> int:
        side = 2 * k + 1  # width of the square one sensor covers
        return (-(-n // side)) * (-(-m // side))  # ceil in each direction

What the code is doing, line by line:

1. Covering a row of length n with intervals of length side needs ceil(n / side).
2. A square cover is the product of a row cover and a column cover, and you can't do better since each sensor covers at most side rows and side columns.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 0 → n · m.
• k large → 1.
• One row.

Complexity: O(1).

Problem: Return the sum of the n smallest numbers that are palindromes in base 10 and in base k.

Solve it on LeetCode ↗

Constraints: 2 ≤ k ≤ 9 · 1 ≤ n ≤ 30

From brute force to the pattern: Checking every integer is hopeless; generating palindromes visits only about √X candidates.

Spot it: Checking every integer is too slow (the 30th can be in the billions). Generate only base-10 palindromes, in increasing order, from their first halves, and test the base-k representation — number-base arithmetic.

Why not another pattern? Scanning all integers up to ~10¹⁰ is far too slow.

Approach:

1. For each length L = 1, 2, …: for each half from 10^(h−1) to 10^h − 1, build the palindrome (odd lengths drop the middle repeat).
2. Convert to base k; if it's a palindrome, add it.
3. Stop after n.

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        def base_k_palindrome(x):
            digits = []
            while x:
                digits.append(x % k)
                x //= k
            return digits == digits[::-1]

        total = found = 0
        length = 1
        while found < n:
            half = (length + 1) // 2
            for first in range(10 ** (half - 1), 10 ** half):  # increasing halves -> increasing palindromes
                s = str(first)
                pal = int(s + s[::-1][length % 2:])  # mirror (skip the middle digit for odd length)
                if base_k_palindrome(pal):
                    total += pal
                    found += 1
                    if found == n:
                        break
            length += 1
        return total

What the code is doing, line by line:

1. For a fixed length, palindromes increase with their first half, so they're produced in order.
2. s[::-1][length % 2:] drops the repeated middle digit for odd lengths.
3. Base-10 palindromes are rare (about √N up to N), so the search is fast.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Single-digit numbers (all palindromes).
• Large k.
• n = 1.

Complexity: About O(√X · log X) for the largest answer X.

Problem: Row 1 is 0; each row replaces 0 with 01 and 1 with 10. Return the k-th symbol of row n.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 30 · 1 ≤ k ≤ 2n ⁻ ¹

From brute force to the pattern: Building rows is O(2ⁿ); counting bits is O(log k).

Spot it: Symbol k (0-indexed k − 1) descends from its parent at (k − 1) // 2, flipped when it's a right child (odd index). Following the bits of k − 1 from the top, it flips once per 1-bit → bit manipulation.

Why not another pattern? Building row n needs 2^(n−1) symbols.

Approach:

1. Return bin(k − 1).count('1') % 2.

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:
        return bin(k - 1).count("1") % 2  # one flip for every right turn on the way down

What the code is doing, line by line:

1. A left child keeps its parent's symbol, a right child flips it.
2. The path from the root to position k − 1 is given by its binary digits; each 1 is a right turn.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 → 0.
• n = 1.
• Last position of a row.

Complexity: O(log k) time, O(1) space.

Problem: Add or subtract any power of 2 per operation. Return the fewest operations to make n zero.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁵

From brute force to the pattern: BFS over integers is slow; the bit scan is O(log n).

Spot it: A bit manipulation greedy: scan from the lowest bit. A single 1 (next bit 0) costs one subtraction. A run of 1s (next bit also 1) is cheaper to clear by adding 1, which turns the run into one carry. This builds the non-adjacent form, which has the fewest non-zero digits.

Why not another pattern? BFS over values works but is far slower and unnecessary.

Approach:

1. While n: if the lowest bit is 1: if the next bit is also 1, n += 1, else n −= 1; count an operation.
2. Shift right.

class Solution:
    def minOperations(self, n: int) -> int:
        ops = 0
        while n:
            if n & 1:
                if n & 2:
                    n += 1  # a run of 1s: one carry clears the whole run
                else:
                    n -= 1  # a lone 1: just subtract it
                ops += 1
            n >>= 1
        return ops

What the code is doing, line by line:

1. Adding 1 to ...0111 gives ...1000: one operation replaces the run.
2. A lone 1 can't be merged with anything, so subtracting it is best.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Power of two → 1.
• All ones (2^k − 1) → 2.
• n = 1.

Complexity: O(log n) time, O(1) space.

Problem: Count the ways to write n as a sum of one or more consecutive positive integers.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 10⁹

From brute force to the pattern: All start/length pairs are O(n²); iterating k is O(√n).

Spot it: Math: a run of k numbers starting at x sums to k·x + k(k − 1)/2. For each length k, check whether n − k(k − 1)/2 is a positive multiple of k. Only k up to about √(2n) can fit.

Why not another pattern? Trying every start and length is O(n²).

Approach:

1. For k = 1, 2, … while k(k − 1)/2 < n:
2. If (n − k(k − 1)/2) % k == 0, count it.

class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        ways = 0
        k = 1
        while k * (k - 1) // 2 < n:  # the smallest run of length k is 1 + 2 + ... + k
            if (n - k * (k - 1) // 2) % k == 0:
                ways += 1  # x = (n - k(k-1)/2) / k is a positive integer
            k += 1
        return ways

What the code is doing, line by line:

1. x = (n − k(k − 1)/2) / k must be a positive integer.
2. Once k(k − 1)/2 ≥ n, x would be ≤ 0, so the loop stops.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 1.
• Powers of two (only the number itself).
• Large n.

Complexity: O(√n) time, O(1) space.

Problem: Return the sum of Hamming distances over all pairs of numbers.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁴ · 0 ≤ nums[i] ≤ 10⁹ · The answer for the given input will fit in a 32-bit integer.

From brute force to the pattern: All pairs: O(32 n²); per-bit counting: O(32 n).

Spot it: Bits are independent → look at one bit position at a time: with c ones among n numbers, exactly c · (n − c) pairs differ at that bit.

Why not another pattern? Comparing all pairs is O(n² · 32).

Approach:

1. For each of 32 bits: c = numbers with that bit set.
2. Add c · (n − c).

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        n = len(nums)
        total = 0
        for b in range(32):
            ones = sum((x >> b) & 1 for x in nums)  # numbers with bit b set
            total += ones * (n - ones)  # each (one, zero) pair differs here
        return total

What the code is doing, line by line:

1. A pair contributes 1 at bit b exactly when one number has it and the other doesn't.
2. Summing over bits counts every differing bit of every pair.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All equal → 0.
• Two numbers.
• Zeros.

Complexity: O(32 · n) time, O(1) space.