Week 15: Greedy, Bit Manipulation, Math and Geometry

Pattern family: Three smaller patterns combined · Time budget: 22 to 26 hours · Prerequisites: Weeks 1 through 14 done. Bring forward the bit operators and divmod from the Week 0 refresher, the sort-by-a-key habit from Week 1, and the cycle-detection idea (fast/slow, or a seen set) from Week 2. · Cold-revisit obligation: Edit Distance, Cheapest Flights Within K Stops.

Overview

This week is three small patterns, not one big one, and the point is breadth: each is its own short toolkit, and an interviewer can pull any of them with no warning. None is hard once you have seen the move it turns on, and that is the danger: if you have not seen the move, you flail; once you have, the problem is a five-minute exercise. So this week is about collecting moves, not building one deep skill.

The three patterns and the single move at the heart of each:

Greedy. Make the locally optimal choice and never reconsider it. The whole pattern lives or dies on one question: can you prove the greedy choice is safe? An unjustified greedy is just a guess that happens to pass the examples.
Bit manipulation. Treat an integer as a row of bits and operate on them directly. Two facts carry most problems: XOR cancels equal values (x ^ x == 0), and n & (n - 1) clears the lowest set bit.
Math and geometry. Mostly index bookkeeping on a matrix (rotate, spiral, mark rows and columns) plus two number tricks: fast exponentiation by squaring, and cycle detection on a sequence you generate.

Because there are three patterns, the move that fires before any code is a routing decision: which of the three is this? The mermaid below is your router.

flowchart TD
    Q["Read the problem"] --> A{"What is the raw material?"}
    A -->|"integers as bits;<br/>duplicates, single-bit asks,<br/>powers of two"| BIT["BIT MANIPULATION<br/>XOR cancels duplicates;<br/>n & (n-1) clears lowest set bit"]
    A -->|"a sequence of choices;<br/>'maximum / minimum / fewest'<br/>with a feasible local move"| GREEDY["GREEDY<br/>take the locally optimal move,<br/>then PROVE it is safe"]
    A -->|"a matrix to transform,<br/>or a number routine<br/>(power, digit cycle)"| MATH["MATH AND GEOMETRY<br/>careful index bookkeeping;<br/>squaring; cycle detection"]
    GREEDY --> P{"Can I prove the greedy<br/>choice never forecloses<br/>a better future?"}
    P -->|no| DP["If a local choice can foreclose<br/>a better global outcome,<br/>this is DP (Weeks 13, 14),<br/>not greedy."]
    P -->|yes| OK["Greedy is safe. Implement<br/>the single forward pass."]

Notice: the first decision is routing (which of the three patterns), and the greedy branch has a second, non-negotiable beat: prove the choice is safe before you trust it. Naming the pattern out loud (principle 1) is what makes this router fire under pressure, and the proof step is what separates a greedy you can defend from a guess.

Warm-Up: Retrieve Before You Begin

Answer from memory, no peeking. This pulls forward the Week 0 refresher facts that this week leans on hardest. Bit manipulation in particular assumes you have the operators cold.

From the refresher: what do ^, &, |, <<, and >> each do to two integers, bit by bit? Give a one-line answer for each.
What does n & (n - 1) do to the binary form of n, and what does the expression n & 1 tell you?
What does divmod(38, 10) return, and how would you use it to peel the digits off a number one at a time?

Check your recall

1. `a ^ b` (XOR): each result bit is 1 when the two input bits differ. `a & b` (AND): each result bit is 1 only when both input bits are 1. `a | b` (OR): each result bit is 1 when at least one input bit is 1. `a << k` (left shift): move every bit `k` places toward the high end, multiplying by `2**k`. `a >> k` (right shift): move every bit `k` places toward the low end, the floor of dividing by `2**k`. 2. Subtracting 1 from `n` flips the lowest set bit to 0 and turns every bit below it into 1; ANDing that back with `n` therefore clears exactly the lowest set bit and leaves the rest alone. So `n & (n - 1)` removes the lowest 1 bit, and looping it until `n` is 0 counts the set bits in O(number of set bits) steps. Separately, `n & 1` is the lowest bit itself: 1 if `n` is odd, 0 if even. 3. `divmod(38, 10)` returns `(3, 8)`: the quotient and the remainder together. The remainder `n % 10` is the last digit; the quotient `n // 10` is what is left. Repeating `n, digit = divmod(n, 10)` peels digits from least significant to most, which is the spine of Happy Number and most digit problems.

Learning objectives

By the end of this week you can:

Route an unseen problem to greedy, bit manipulation, or math/geometry from its cues, and say out loud which one and why.
Justify a greedy choice with an exchange argument, and recognize when no such argument exists (so the problem is really DP).
Apply the two bit facts (x ^ x == 0, and n & (n - 1) clears the lowest set bit) to cancel duplicates and count or manipulate bits without converting to strings.
Explain why a bit problem that relies on overflow needs a 32-bit mask in Python, and write that mask.
Construct an in-place matrix transform (rotate, spiral, zero-marking) and an iterative fast-exponentiation, and state precisely why each is correct.
Analyze the time and space complexity of every solution and name what dominates at scale.
Defend every line of each solution you commit, from memory, with no AI open.

Recognition cue

There is no single cue this week; there are three, and the first skill is telling them apart.

Greedy. The problem asks for a maximum, a minimum, or a count of something, and at each step there is an obvious “best move right now” that you suspect you can commit to without looking ahead. The trigger word is the optimization (“fewest jumps”, “maximum intervals kept”), and the trap is that the obvious move is not always safe; greedy is only the pattern once you can prove it is.
Bit manipulation. The problem is about the bits of an integer: a value that appears an odd number of times among duplicates, counting set bits, reversing or summing at the bit level, or anything that says “powers of two”. The tell is that the integers are being treated as patterns of bits, not as quantities.
Math and geometry. The problem hands you a matrix to rotate, traverse in a spiral, or mark, or it is a self-contained number routine such as raising to a power or following a sequence of generated numbers to see whether it cycles. The tell is that the work is index bookkeeping or a closed-form numeric trick, not a data-structure pattern.

If a problem looks greedy but you cannot prove the local choice is safe, treat it as dynamic programming (Weeks 13 and 14) until proven otherwise. The cost of a wrong greedy is a solution that passes the samples and fails the judge.

Core concepts to internalize this week

This week has three concept clusters, one per sub-pattern. Treat them as three short chapters.

Cluster 1: Greedy

The greedy contract. A greedy algorithm makes the choice that looks best right now and never revisits it. That is fast and simple, but it is only correct if a locally optimal choice is also part of some globally optimal solution. You must argue that, not assume it.
The exchange argument. The standard proof technique: assume an optimal solution that differs from the greedy one, then show you can swap (exchange) a piece of it for the greedy choice without making it worse. If every optimal solution can be edited toward the greedy choice at no cost, the greedy choice is safe. You do not write a formal proof in an interview, but you state the swap in one sentence.
The “farthest reach” family. Jump Game and Jump Game II both reduce to tracking the farthest index reachable so far in a single left-to-right pass. You never enumerate paths; you carry one number (the frontier) and extend it. This is the cleanest greedy in the week and the canonical walks it.
Sort, then sweep. Many interval and partition greedies start by sorting on the right key (by end time for Non-overlapping Intervals; by last occurrence for Partition Labels), after which one linear pass with a running boundary does the job. Choosing the sort key is the greedy insight.

Common misconception. “The locally optimal move is the globally optimal move, so I can just take the biggest/closest thing each step.” Reality. Locally optimal is not always globally optimal. Sometimes the greedy move forecloses a strictly better future (this is exactly why greedy fails on Coin Change [1,3,4] making 6, from last week). You must justify the greedy choice with an exchange argument before you trust it. If you cannot, the problem is DP, not greedy, and a greedy will pass the examples and fail on a hidden case. State the justification out loud; interviewers ask for it directly.

Cluster 2: Bit Manipulation

XOR cancels duplicates. x ^ x == 0 and x ^ 0 == x, and XOR is commutative and associative, so XORing a whole list together cancels every value that appears an even number of times and leaves the one that appears an odd number of times. That single fact solves Single Number in one pass and O(1) space.
n & (n - 1) clears the lowest set bit. Subtracting 1 flips the lowest 1 to 0 and sets every bit below it; ANDing with n clears exactly that lowest 1. Looping it counts set bits in as many steps as there are 1s (Number of 1 Bits), which beats checking all 32 positions when the number is sparse.
Build bits with shift-and-or; read them with mask-and-shift. To reverse the bits of a 32-bit number, pull the low bit with n & 1, push it into an accumulator with result = (result << 1) | bit, then shift n right; do it 32 times (Reverse Bits). To add without +, the sum-without-carry is a ^ b and the carry is (a & b) << 1, looped until there is no carry (Sum of Two Integers).
Overlap with DP. Counting Bits is a bit problem solved by a one-line DP recurrence: count[i] = count[i >> 1] + (i & 1). The number of set bits in i equals the set bits in i with its low bit dropped, plus that low bit. This is a deliberate bridge back to Week 13.

Common misconception. “Bit tricks work the same in every language, so I never have to think about width.” Reality. In languages with fixed-width integers (C, Java), bit tricks silently wrap at 32 or 64 bits, and many tricks (the no-+ addition, simulated overflow) depend on that wrap. Python integers are arbitrary precision: they never overflow, so a naive bit loop that relies on wrap can spin forever or produce a giant number instead of a negative one. When a problem is specified in 32-bit terms, you must impose the width yourself: mask with & 0xFFFFFFFF to keep 32 bits, and reinterpret the top bit as a sign by hand. Sum of Two Integers is the problem that forces this, and its README spells out the mask.

Cluster 3: Math and Geometry

In-place matrix transforms. Rotating an image 90 degrees is “transpose, then reverse each row”; both steps happen inside the same grid with swaps, so the space is O(1) extra. The discipline is index bookkeeping: get the swap indices right and prove you touch each cell the correct number of times.
Boundary-shrinking traversal. Spiral Matrix walks the four edges (top row left-to-right, right column top-to-bottom, bottom row right-to-left, left column bottom-to-top), then shrinks the four boundaries inward and repeats. The bugs live in the boundary checks when the matrix is not square; you guard the bottom row and left column with if top <= bottom and if left <= right.
Marking with the array itself. Set Matrix Zeroes asks you to zero a whole row and column for each zero found. The naive fix uses O(m + n) sets of indices; the in-place trick uses the first row and first column as the marker storage to reach O(1) extra space. Either is acceptable; you must be able to state the space you used and why.
Number routines: squaring and cycles. Fast exponentiation computes x**n in O(log n) multiplications by squaring the base and halving the exponent, reading the exponent bit by bit (Pow(x, n)). Cycle detection on a generated sequence (the digit-square sequence in Happy Number) is the same idea as Week 2’s fast/slow pointers: either keep a seen set, or run two pointers at different speeds, to decide whether the sequence reaches 1 or loops forever.

Common misconception. “An in-place transform just means I do not return a new matrix; I can still scribble freely as I go.” Reality. In-place means you mutate the input under a real constraint: once you overwrite a cell, its old value is gone, so the order of operations is part of the correctness. Rotate Image is wrong if you reverse before you transpose, or if you transpose the whole grid instead of one triangle (you would swap every pair twice and undo the transpose). Set Matrix Zeroes is wrong if you zero a row in the first pass, because that fresh zero then triggers spurious zeros in later rows. The rule: decide what you read and what you write, and never read a cell after you have clobbered the value you still needed.

Python idioms this week

You are not yet expected to be fluent, so here is the toolbox this week uses. If any is unfamiliar, open the Python refresher before Monday; the bit operators are introduced in the refresher’s Section 1 bit-operations notes and expanded here, divmod is in the same section, and the two division traps matter this week too.

Bit operators: ^ (XOR), & (AND), | (OR), ~ (NOT), << and >> (shifts). One-bit reads: n & 1 for the low bit, n >> 1 to drop it.
The clear-lowest-set-bit idiom n & (n - 1), looped while n is nonzero, to count or strip set bits.
32-bit masking value & 0xFFFFFFFF to simulate fixed width in Python’s unbounded integers, and reinterpreting the high bit as a sign by hand.
divmod(n, 10) (and divmod(n, 2)) to take a quotient and remainder in one step when peeling digits or bits.
sorted(intervals, key=lambda iv: iv[1]) and list.sort(key=...) to sort on the right key before a greedy sweep.
In-place list moves: list.reverse(), and the swap a[i], a[j] = a[j], a[i] (and its 2-D form m[i][j], m[j][i] = m[j][i], m[i][j]).
A set for “have I generated this number before” cycle detection (Happy Number), the same membership reflex from Week 1.

These are tools you are allowed to know cold in an interview. The pattern (which of the three this is, why the greedy is safe, why the bit identity holds) is the part you build yourself.

Pattern Card requirement

This week you write three Pattern Cards, one per sub-pattern, because there are three distinct recognition cues to drill. Write them before you start the canonical:

.tutor/pattern-cards/greedy.md
.tutor/pattern-cards/bit-manipulation.md
.tutor/pattern-cards/math-geometry.md

Each card must contain:

The recognition cue, in your own words (what makes you reach for this pattern and not the other two).
The algorithmic skeleton in pseudocode (for greedy: sort-or-scan, then the running quantity and the commit step; for bit: the identity you exploit and the loop shape; for math/geometry: the index bookkeeping or the squaring/cycle loop).
Time and space complexity, general form.
Three edge cases (good starts: greedy: a single element, an already-optimal input, an input where the obvious greedy is wrong; bit: zero, a single bit set, the all-ones value; math/geometry: a 1x1 matrix, a single row or column, a negative or zero exponent).
One war story (a bug you actually hit this week); fill this in at the end of the week.

The first four sections of all three cards must be present before you start the canonical deep-dive. The tutor will probe the cards; it will not write any of them for you.

Canonical deep-dive

Problem: Three short tricks, one per sub-pattern (Jump Game, Single Number / Number of 1 Bits, and Pow(x, n)).

Because this week is three patterns, the canonical is not one problem; it is one guided walk-through that teaches the single “aha” move at the center of each sub-pattern, in canonical/three-tricks.md. It covers the greedy exchange argument on Jump Game, the two bit identities (x ^ x == 0 and n & (n - 1)) on Single Number and Number of 1 Bits, and fast exponentiation by squaring on Pow(x, n). Work it there. As always it is a guided walk-through, not an answer key: it shows you how to think and stops short of code you could paste. You write the Python yourself, in your own work repo, and LeetCode’s judge confirms it, not the tutor.

Practice set

Fifteen problems, grouped by sub-pattern. Seven are core (required) and the rest are optional stretch; the split is marked inside each group below. Do the groups in order (greedy, then bit, then math/geometry), and within a group do the core problems before the stretch ones; the listed order moves from the cleanest example of the move to the ones that stress it. Each problem has its own folder under practice/ with the problem link, a complexity target for you to fill in, and the debrief template.

Several of the bit and math problems are genuinely short once the move is in hand, so for those the 25-minute struggle floor is a ceiling, not a quota: if you have named the pattern and you are clearly converging, treat the floor as a 10-to-15-minute honest attempt rather than a full 25. The greedy problems and the proof-heavy ones still earn the full floor.

Greedy (do these first)

Core (required):

Jump Game (practice/jump-game/). The cleanest “farthest reach” greedy: can you reach the last index? Track the frontier in one pass.
Gas Station (practice/gas-station/). A circular-route greedy with a clean exchange argument: if the running tank goes negative at station i, no start in the stretch you just covered can work.

Optional stretch (do if you have time; recommended before the Week 16 marathon):

Jump Game II (practice/jump-game-ii/). The same frontier idea, now counting the fewest jumps. The greedy is a level-by-level expansion.
Partition Labels (practice/partition-labels/). Sort-free greedy: precompute each character’s last index, then sweep and cut when the current window closes.
Non-overlapping Intervals (practice/non-overlapping-intervals/). The classic sort-by-end-then-sweep greedy; the sort key is the whole insight.

Bit Manipulation

Core (required):

Single Number (practice/single-number/). XOR the whole list; duplicates cancel. One pass, O(1) space.
Number of 1 Bits (practice/number-of-1-bits/). Count set bits with n & (n - 1) looped until zero.
Counting Bits (practice/counting-bits/). A bit problem that is secretly a one-line DP: count[i] = count[i >> 1] + (i & 1).

Optional stretch (do if you have time; recommended before the Week 16 marathon):

Reverse Bits (practice/reverse-bits/). Build the result with shift-and-or across all 32 positions.
Sum of Two Integers (practice/sum-of-two-integers/). Add without +: XOR is the sum, AND-shifted is the carry. This is the problem that forces the 32-bit mask in Python; its README spells out the subtlety.

Math and Geometry

Core (required):

Pow(x, n) (practice/powx-n/). Fast exponentiation by squaring in O(log n); handle the negative exponent.
Rotate Image (practice/rotate-image/). In place: transpose, then reverse each row. Order matters.

Optional stretch (do if you have time; recommended before the Week 16 marathon):

Spiral Matrix (practice/spiral-matrix/). Walk four shrinking boundaries; guard the bottom row and left column for non-square inputs.
Set Matrix Zeroes (practice/set-matrix-zeroes/). Mark first, zero second; the in-place version uses row 0 and column 0 as markers.
Happy Number (practice/happy-number/). Generate the digit-square sequence and detect a cycle (a seen set, or fast/slow pointers from Week 2).

The seven core problems (Jump Game, Gas Station, Single Number, Number of 1 Bits, Counting Bits, Pow(x, n), Rotate Image) are the required set and cover the canonical “aha” move of every sub-pattern; the eight stretch problems deepen each move and are the best warm-up for the Week 16 marathon. Each problem follows the five-beat rhythm.

The five-beat rhythm (every problem)

Pattern Card is written (all three, done Monday).
Name the pattern aloud (which of the three, and why) and write your approach as a plain-English comment before any code.
Struggle floor: 25 minutes unaided (a 10-to-15-minute honest attempt is enough on the short bit and math problems flagged in the Practice set, once you have named the pattern and are clearly converging).
Hint ladder if needed: six rungs, one per ask.
Debrief: the five questions, in your commit message, before the next problem.

Reflect

Ten minutes in your notebook, in writing:

Explain it back: in three sentences, state the one move at the center of each sub-pattern (greedy, bit, math/geometry) to a peer who just finished Week 14.
Connect: Counting Bits is solved with a DP recurrence, and Happy Number reuses Week 2’s cycle detection. Pick one and write two sentences on how this week’s problem is the same idea wearing different clothes.
Monitor: of the three patterns, which one’s recognition cue is still the fuzziest for you? Write the one sentence that would make you reach for it on sight.

Knowledge Check

Answer from memory first. Items marked ⟲ are spaced callbacks to earlier material.

(Greedy) What is an exchange argument, and why is it the thing that separates a correct greedy from a lucky guess?
(Greedy) In Jump Game, what single quantity do you carry through the one pass, and how do you update it and decide failure?
(Bit) Why does XORing an entire list together leave exactly the element that appears an odd number of times?
(Bit) What does n & (n - 1) do to n, and how does that give you an O(set-bits) way to count 1s?
(Bit) Python integers never overflow. Why does that force you to use a & 0xFFFFFFFF mask in Sum of Two Integers, when a C or Java solution does not need one?
(Math/Geometry) Rotate Image is “transpose, then reverse each row.” Why does doing the two steps in the wrong order, or transposing the whole grid instead of one triangle, give the wrong answer?
(Math/Geometry) Fast exponentiation computes x**n in O(log n) multiplications. What are you squaring, what are you halving, and how does the binary form of n come into it?
⟲ From Week 2: Happy Number asks whether a generated sequence reaches 1 or cycles forever. What two techniques detect the cycle, and what is the space cost of each?
⟲ From Week 13: Counting Bits has the recurrence count[i] = count[i >> 1] + (i & 1). State the one-sentence reason this recurrence is correct.

Answer key

1. An exchange argument assumes an optimal solution that differs from the greedy one and shows you can swap a piece of it for the greedy choice without making the solution worse; if every optimal can be edited toward the greedy choice at no cost, the greedy choice is safe. It is what separates a correct greedy from a guess because without it you have only checked that the move looks good locally and passes the examples, not that it is ever wrong on a hidden case. 2. You carry the farthest index reachable so far (the frontier). At each index `i`, if `i` is past the frontier you can never reach it, so return False; otherwise extend the frontier to `max(frontier, i + nums[i])`. You succeed if the frontier reaches (or passes) the last index. 3. XOR is commutative and associative, `x ^ x == 0`, and `x ^ 0 == x`. So reordering the list to pair up equal values, every value appearing an even number of times cancels to 0, and the lone odd-count value XORed against 0 survives unchanged. 4. Subtracting 1 flips the lowest set bit of `n` to 0 and sets all bits below it to 1; ANDing with `n` clears exactly that lowest set bit and leaves the rest. Looping `n &= n - 1` and counting iterations runs once per set bit, so it is O(number of 1s), faster than scanning all 32 positions on sparse numbers. 5. In C or Java the addition loop terminates because the carry, shifted left, eventually falls off the fixed 32-bit (or 64-bit) edge and the value naturally wraps to a negative number via two's complement. Python integers are unbounded, so that carry never falls off: it keeps growing and the loop can spin forever (and a negative result is never represented as a wrapped pattern). You impose the width yourself by masking with `& 0xFFFFFFFF` each step and reinterpreting the top bit as the sign at the end. 6. The two operations do not commute: "transpose then reverse rows" rotates clockwise, but "reverse rows then transpose" rotates counter-clockwise (or otherwise scrambles), so order is part of the algorithm. Transposing the *whole* grid swaps every off-diagonal pair twice, which is a no-op (you undo your own transpose); you must transpose only one triangle (for example `j` from `i + 1` upward) so each pair is swapped exactly once. 7. You square the base `x` and halve the exponent `n` each step; reading `n` bit by bit, whenever the current low bit is 1 you multiply the running result by the current squared base. This works because `x**n` is the product of `x**(2**k)` over the bit positions `k` set in `n`, and squaring the base each step produces exactly those `x**(2**k)` values, giving O(log n) multiplications. 8. A `seen` set: store every number generated and stop when one repeats; O(n) extra space for the numbers seen before a repeat. Fast/slow pointers (Floyd's cycle detection from Week 2): advance one sequence one step and another two steps and stop when they meet; O(1) extra space. Both decide "reaches 1" versus "loops". 9. Dropping the lowest bit of `i` (that is `i >> 1`) gives a strictly smaller number whose set-bit count is already known, and `i & 1` adds back the single low bit you dropped; so the set bits of `i` equal the set bits of `i >> 1` plus that low bit. (`count[0] = 0` anchors the recurrence.)

Cold revisit

This Friday, before any new work, re-solve two prior problems cold: no notes, no prior code open, no AI, the standard 25-minute floor on each. The full instructions are in revisit.md.

Edit Distance (Week 14, 2-D Dynamic Programming). A blind re-solve. Do not look at which pattern it is until you have named it yourself.
Cheapest Flights Within K Stops (Week 12, Advanced Graphs). A blind re-solve, same rules.

Neither is this week’s pattern, and that is the point: greedy, bit, and math are short and seductive, so this Friday reaches back to the two hardest, densest things you built recently and keeps them from going stale while you spend the week on lighter material. Edit Distance is the canonical two-string DP from Week 14, so it keeps the state-definition skill alive. Cheapest Flights is the Advanced Graphs canonical from Week 12 (state expansion, solved Bellman-Ford-by-rounds), the heaviest, most algorithm-dense week in the course; this is its one fixed cold re-test before the marathon, so recognizing it cold and rebuilding the (node, stops_used) state from a blank file is exactly the muscle to exercise here. Debrief each at the end and log the outcome in .tutor/revisit-log.md.

How to know you are done with this week

Three Pattern Cards complete at .tutor/pattern-cards/greedy.md, bit-manipulation.md, and math-geometry.md, each including the war-story field.
Canonical deep-dive done: the three tricks worked through, with at least Jump Game, Single Number, Number of 1 Bits, and Pow(x, n) implemented yourself in your own work repo, plus your short reflection.
The seven core practice problems solved (Jump Game, Gas Station, Single Number, Number of 1 Bits, Counting Bits, Pow(x, n), Rotate Image), each with a five-question debrief in its commit message. The eight optional stretch problems are recommended before the Week 16 marathon but are not required to close the week.
.tutor/revisit-log.md updated by the tutor with this week’s problems and the two cold revisits, with dates.
.tutor/progress.md updated to “Week 15 complete; ready for Week 16.”

If any of the above is missing, the week is not done. The tutor will not advance you to Week 16 until all five are present.

Resources

Free, no account required:

[Article] Greedy algorithms, the idea: https://en.wikipedia.org/wiki/Greedy_algorithm
[Article] Exchange argument (proof technique): https://en.wikipedia.org/wiki/Exchange_argument
[Article] Bitwise operations: https://en.wikipedia.org/wiki/Bitwise_operation
[Article] Exponentiation by squaring: https://en.wikipedia.org/wiki/Exponentiation_by_squaring
[Docs] Python bitwise operators and integer methods: https://docs.python.org/3/library/stdtypes.html#bitwise-operations-on-integer-types
[Docs] Python divmod: https://docs.python.org/3/library/functions.html#divmod

Week 15: Greedy, Bit Manipulation, Math and Geometry

Overview

Warm-Up: Retrieve Before You Begin

Learning objectives

Recognition cue

Core concepts to internalize this week

Cluster 1: Greedy

Cluster 2: Bit Manipulation

Cluster 3: Math and Geometry

Python idioms this week

Pattern Card requirement

Canonical deep-dive

Practice set

Greedy (do these first)

Bit Manipulation

Math and Geometry

The five-beat rhythm (every problem)

Reflect

Knowledge Check

Cold revisit

How to know you are done with this week

Resources

Table of contents