Canonical Deep-Dive: Three Tricks (Greedy, Bit, Math)

Problems: Jump Game (https://leetcode.com/problems/jump-game/), Single Number (https://leetcode.com/problems/single-number/), Number of 1 Bits (https://leetcode.com/problems/number-of-1-bits/), Pow(x, n) (https://leetcode.com/problems/powx-n/) The lesson: the single “aha” move at the center of each of this week’s three sub-patterns.

This week is three small patterns, so the canonical is three small deep-dives instead of one big one. Each section below teaches one move: the move you have to have seen before the problems in that group feel easy. As always, this is a guided walk-through, not an answer key. It explains how to think and shows the key relations and invariants in words, and it stops short of assembled, paste-runnable functions on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Read all three before you start the practice set. They are short.

Trick 1 (Greedy): the exchange argument, on Jump Game

Problem, restated. You are given an array nums where nums[i] is the maximum number of steps you may jump forward from index i. You start at index 0. Return whether you can reach the last index. Example: [2,3,1,1,4] returns True (from 0 you can step to index 1, then jump 3 to the last index); [3,2,1,0,4] returns False (every route lands on the 0 at index 3 and stalls).

The slow way first

The brute force is to try every jump from every reachable position recursively: from i, try each landing in 1..nums[i], and ask whether any of them can reach the end. That is exponential, because the same index gets re-explored through many different jump sequences. Hold that baseline in mind; the greedy collapses it to one pass.

The greedy claim

Here is the move. Sweep left to right and carry a single number: farthest, the farthest index you can reach given everything seen so far. At each index i:

  • If i is beyond farthest, you can never stand on i, so the end is unreachable: stop and report failure.
  • Otherwise you can stand on i, so update farthest = max(farthest, i + nums[i]).

If the sweep finishes (or farthest reaches the last index), the end is reachable.

That is the whole algorithm: one variable, one pass, O(n) time and O(1) space. It feels too cheap. The work of this section is convincing yourself it is correct, because “it passed the two examples” is not a reason.

Why the greedy choice is safe (the exchange argument)

The thing to prove is: tracking only the single farthest-reachable index loses no information you needed. You are throwing away the entire set of reachable indices and keeping one number; why is that safe?

State the invariant precisely: after processing indices 0..i, the value farthest is the maximum index reachable using some sequence of jumps that stays within 0..i. Two things make this hold:

  1. Reachability is an interval, not a scattered set. If you can reach index k, you can reach every index from 0 up to k, because from any reachable position you may jump fewer steps than the maximum (you can always under-jump). So “the reachable set” is fully described by its right endpoint, and that endpoint is exactly farthest. Keeping the single number farthest loses nothing, because the set it stands for has no holes.
  2. Extending the frontier never needs a worse choice. This is the exchange step. Suppose some optimal route reaches the end. Consider the first index i where the greedy frontier and that route would “disagree” about how far you can get. Because every index up to farthest is reachable (point 1), the greedy is allowed to stand on the exact index the optimal route used, and from there it takes max over i + nums[i], which is at least as far as whatever the optimal route jumps to. So you can swap the optimal route’s next landing for the greedy’s farther (or equal) one without ever reducing reach. Repeating the swap turns the optimal route into the greedy one without ever making it worse. Therefore the greedy reaches at least as far as any route, at every step.

That is an exchange argument in plain words: take any solution, show you can edit it toward the greedy choice at no cost, conclude the greedy is safe. In an interview you say exactly the two sentences above (“reachability has no holes, so one number suffices; and extending to the max never costs you anything, so I never need to reconsider”). You do not write symbols.

Contrast: when the same instinct is a trap

Greedy is only a pattern when the exchange argument exists. Last week’s Coin Change is the cautionary twin: “always take the largest coin that fits” is the same locally-greedy instinct, and it is wrong ([1,3,4] to make 6 greedily takes 4+1+1, three coins, missing 3+3, two coins), because committing to the big coin forecloses a better future and there is no exchange that fixes it. The difference is structural: in Jump Game a local over-reach never hurts (you can always under-jump later), so the swap goes through; in Coin Change it can hurt, so it does not. Before you trust any greedy, ask which world you are in.

The key insight, in one sentence

Reachability in Jump Game is a hole-free interval, so its right endpoint is all the state you need; extending that endpoint greedily never forecloses anything, which is exactly the exchange argument that makes the one-pass, O(1)-space solution correct.

Jump Game II (the next practice problem) is the same frontier idea with a counter: you expand the frontier in “levels”, and each time you exhaust the current level’s reach you spend one jump and adopt the farthest reach discovered during it. Same invariant, one more variable.

Trick 2 (Bit): XOR cancels, and n & (n - 1) clears the lowest set bit

Two identities carry most bit problems. This section proves both and shows each on its home problem.

Identity A: x ^ x == 0, and what it does to a list

XOR (^) compares two numbers bit by bit and sets a result bit to 1 exactly when the input bits differ. Three facts follow immediately:

  • x ^ x == 0 (every bit matches itself, so no bit differs).
  • x ^ 0 == x (differing from all-zeros leaves x unchanged).
  • XOR is commutative and associative, so you may reorder and regroup a chain of XORs however you like.

Single Number, restated. Every element of nums appears exactly twice except one, which appears once; find the single one. Example: [4,1,2,1,2] returns 4.

Put the three facts together. XOR the entire list into one accumulator. Because you may reorder freely, mentally group each duplicated pair together: each pair is x ^ x == 0, so every value that appears twice contributes nothing. What remains is 0 ^ (the lone value) == the lone value. One pass, O(n) time, O(1) space, no hash set needed. The “aha” is that XOR is a self-cancelling accumulator: feeding it a value an even number of times is the same as never feeding it at all.

This generalizes: XOR a list and you are left with the XOR of exactly the values that appear an odd number of times. (That is why the same trick finds “the one number appearing an odd number of times” and, with a little more work, two singletons.)

Identity B: n & (n - 1) clears the lowest set bit

Look at what subtracting 1 does to a binary number. Find the lowest 1 bit of n. Everything below it is 0. Subtracting 1 turns that lowest 1 into a 0 and turns all the 0s below it into 1s; everything above the lowest 1 is untouched. Now AND n with n - 1: above the lowest set bit the two numbers are identical (those bits survive), at the lowest set bit you have 1 & 0 == 0 (it is cleared), and below it you have 0 & 1 == 0 (still zero). Net effect: n & (n - 1) is n with exactly its lowest set bit removed, and nothing else changed.

Make it concrete. n = 12 is 1100. n - 1 = 11 is 1011. 1100 & 1011 = 1000, which is 8: the lowest set bit (the 4) is gone, the high bit stays. Do it again: 1000 & 0111 = 0000. Two operations cleared two set bits and reached zero.

Number of 1 Bits, restated. Given a 32-bit integer n, return how many bits are set to 1 (its Hamming weight). Example: 11 is 1011, which has 3 set bits.

The obvious method checks all 32 positions: (n >> k) & 1 for each k, always 32 steps. The n & (n - 1) method is better when the number is sparse: loop n = n & (n - 1) and count iterations until n is 0. Each iteration removes exactly one set bit (Identity B), so the loop runs once per 1 bit, no more. On a number with three set bits it does three iterations regardless of how wide the integer is. The “aha” is that you can iterate over the set bits themselves rather than over all bit positions.

The key insight, in one sentence

Treat an integer as bits and two identities do most of the work: XOR is a self-cancelling accumulator (x ^ x == 0), so XORing a list leaves the odd-count value; and n & (n - 1) deletes the lowest set bit, so looping it iterates exactly once per 1 bit.

A note you will need next door, for the other bit problems in the practice set:

  • Counting Bits combines this with last week’s DP. The set-bit count of i is the count of i >> 1 (the same number with its low bit dropped) plus i & 1 (the low bit you dropped), so count[i] = count[i >> 1] + (i & 1) fills a table in O(n).
  • Reverse Bits is built bit by bit with shift-and-or: read the low bit of the input with n & 1, push it onto an accumulator with result = (result << 1) | bit, shift the input right, and repeat for all 32 positions. You build the reversed number one bit at a time instead of indexing into it.
  • Sum of Two Integers leans on XOR-as-sum-without-carry plus (a & b) << 1-as-carry, looped until there is no carry, with the Python-specific 32-bit-mask wrinkle its own README spells out.

Trick 3 (Math): fast exponentiation by squaring, on Pow(x, n)

Problem, restated. Implement pow(x, n): raise the float x to the integer power n. n can be negative. Examples: (2.0, 10) returns 1024.0; (2.0, -2) returns 0.25; (2.1, 3) returns about 9.261.

The slow way first

Multiply x by itself n times: O(n) multiplications. For the constraint sizes on this problem (n up to about two billion in magnitude) that is far too slow, and it is the baseline you are improving away from.

The squaring idea

The exponent has a binary form, and exponentiation turns that binary form into a product. Write n in binary. Then

x**n = product of  x**(2**k)  over every bit position k that is set in n

because n is the sum of those powers of two, and x raised to a sum is the product of x raised to each piece. The pieces x**(2**k) are easy to generate in sequence: x**1, then square it to get x**2, square again for x**4, then x**8, and so on. Each squaring doubles the exponent, so after k squarings you hold x**(2**k).

So sweep the bits of n from low to high. Keep a running result (starting at 1.0) and a running base (starting at x, which is x**(2**0)). At each step:

  • If the current low bit of n is 1, fold the current base into the answer: result *= base.
  • Square the base for the next position: base *= base.
  • Drop the bit you just handled: n >>= 1 (or n //= 2).

Stop when n reaches 0. The number of steps is the number of bits in n, which is about log2(n), so this is O(log n) multiplications instead of O(n). That is the “aha”: reading the exponent bit by bit, you only ever need log n squarings, and you multiply in just the squared bases whose bit is set.

The negative-exponent detail

x**(-n) is 1 / (x**n). Handle it once, up front: if n is negative, replace x with 1 / x and n with -n, then run the same loop. (Be aware that the most negative 32-bit integer cannot simply be negated in fixed-width languages; in Python integers are unbounded so -n is safe, but it is worth knowing why the C version needs care. State that you know it.)

Why it is correct

The loop maintains an invariant: at every step, result times base raised to the remaining exponent equals the original x**n. Initially result == 1 and base ** n == x ** n, so it holds. Each step either (a) the low bit is 0, and you square the base while halving the remaining exponent, which leaves base ** remaining unchanged; or (b) the low bit is 1, and you peel one factor of the current base into result before squaring, which also preserves the product. When the remaining exponent hits 0, base ** 0 == 1, so result alone is the answer. That invariant is what you state in an interview to justify the squaring.

The key insight, in one sentence

The binary form of the exponent turns x**n into a product of log n repeatedly-squared bases, one factor per set bit, so reading n bit by bit while squaring the base computes the power in O(log n) multiplications instead of O(n).

A note you will need next door, for the rest of the math and geometry practice set. The other “number routine” is Happy Number: it is not about squaring the base but about following a generated sequence (replace n by the sum of the squares of its digits, repeatedly) and detecting whether it cycles. That cycle detection is Week 2’s fast/slow pointer idea (or a seen set), reused.

The geometry half is three in-place matrix transforms, each a discipline of index bookkeeping rather than a number trick:

  • Rotate Image rotates 90 degrees clockwise by transposing the matrix and then reversing each row, both inside the same grid. The order matters: transpose then reverse rotates clockwise, and transposing the whole grid (instead of one triangle) undoes itself, so each off-diagonal pair must be swapped exactly once.
  • Spiral Matrix walks four shrinking boundaries: the top row left to right, the right column top to bottom, the bottom row right to left, the left column bottom to top, then moves the four boundaries inward and repeats. The bugs live in the boundary guards for non-square inputs, where the bottom row and left column need an if check before they run.
  • Set Matrix Zeroes is mark-first, act-second: you cannot zero a row or column as you scan, because the fresh zeros would trigger spurious ones, so you record which rows and columns must be zeroed first and apply them in a second pass (the O(1)-space version stores those marks in row 0 and column 0).

Your work this week

  1. Implement Jump Game yourself, the one-pass farthest greedy, in your own work repo. Before you code, write the exchange argument as a one-line comment (“reachability is a hole-free interval, so its right endpoint is all the state I need, and extending it greedily never forecloses anything”). Then check [2,3,1,1,4] returns True and [3,2,1,0,4] returns False, and submit to the judge.
  2. Implement Single Number (XOR the list) and Number of 1 Bits (n & (n - 1) loop). For each, write the identity you are exploiting as a comment first. Confirm [4,1,2,1,2] gives 4 and that 11 has 3 set bits, then submit both.
  3. Implement Pow(x, n) with the squaring loop, handling the negative exponent up front. Confirm (2.0, 10) is 1024.0, (2.0, -2) is 0.25, and (2.1, 3) is about 9.261, then submit.
  4. Commit each with a five-question debrief in the message. In answer 3 (complexity), state the exact cost: Jump Game O(n) time / O(1) space; Single Number O(n) / O(1); Number of 1 Bits O(set bits) / O(1); Pow O(log n) multiplications / O(1).

When you can explain, from memory and with no AI open, (a) the two-sentence exchange argument that makes Jump Game’s greedy safe, (b) why XORing a list isolates the odd-count value and why n & (n - 1) removes one set bit, and (c) why reading the exponent’s bits while squaring computes a power in log n steps, you own the three moves at the center of this week. Those three explanations are exactly what an interviewer probes for, and they are the templates you reuse across all fifteen practice problems.