Hi👋SpeedAlgo • Deliberate Practice & Cognitive Ergonomics for Software Engineers

An interactive algorithm mastery and technical interview preparation platform published by Hi👋WebEnterprise. Built for senior and staff software engineers preparing for rigorous coding screens at top tech companies (FAANG/MAMAA).

13 Core Algorithmic Patterns & 225 Practice Problems

  • 1. Two Pointers (16 Paradigms, 43 Problems): Opposite ends, sorted pair sums, palindrome verification, trapping rain water, 3Sum, container with most water — includes the Sliding Window and Fast & Slow Pointers paradigms (contiguous subarray invariants, longest substrings, Floyd's cycle detection, linked list middle).
  • 2. Binary Search (9 Paradigms, 14 Problems): Monotonic predicate partitioning (feasible(x)), boundary search, rotated sorted arrays, square roots, minimum ship capacity, median of two sorted arrays, matrix median on value range.
  • 3. Bit Manipulation (5 Paradigms, 11 Problems): Counting set bits, XOR cancellation, bit reversal, bitmask pairing, maximum XOR with a bitwise trie.
  • 4. Math & Geometry (8 Paradigms, 14 Problems): Sieve of Eratosthenes, integer/roman conversions, modular arithmetic, geometric simulation.
  • 5. Tree/Graph Depth-First Search (15 Paradigms, 24 Problems): Path sums, lowest common ancestor, tree diameter, validating BSTs, tree DP (House Robber III, Binary Tree Cameras).
  • 6. Tree/Graph Breadth-First Search (5 Paradigms, 12 Problems): Level-order traversals, shortest path in unweighted graphs, zig-zag traversals, rotting oranges, word ladders.
  • 7. Graphs (12 Paradigms, 22 Problems): Topological sort, cycle detection, Dijkstra's algorithm, bipartite graph validation, network delay.
  • 8. Backtracking (6 Paradigms, 14 Problems): Subsets, permutations, combinations, constraint satisfaction, pruning, N-Queens, Sudoku solver.
  • 9. Dynamic Programming (13 Paradigms, 28 Problems): Memoization vs tabulation, 0/1 knapsack, unbounded knapsack, coin change, edit distance, longest common subsequence.
  • 10. Heap / Priority Queue (9 Paradigms, 11 Problems): Running medians, top-k elements, interval scheduling, IPO, k-way merges.
  • 11. Advanced Data Structures (7 Paradigms, 17 Problems): Trie (prefix tree), Union-Find (Disjoint Set Union), LRU Cache, LFU Cache, range-sum queries with updates.
  • 12. Stack (5 Paradigms, 9 Problems): Next greater element, largest rectangle in histogram, remove k digits, decode string, min stack.
  • 13. Intervals & Greedy (2 Paradigms, 6 Problems): Merge intervals, interval scheduling, meeting rooms by sweep line, jump game.

4-Stage Deliberate Practice Framework

  1. Stage 1 (Compare & Learn): Read the pattern's mental model, loop invariant and Big-O proof, compare the pattern's template with the problem's solution side by side, and use the step-by-step debugger. The solution can also be shown in C#, Java, TypeScript, C++, Go or Rust for almost every problem.
  2. Stage 2 (Active Recall): Rebuild the solution from memory in a code editor, with an invariant checklist and optional progressive hints, and check it against a judged test suite.
  3. Stage 3 (AI Interview Coach, coming soon): A mock-interview stage still in development; for now, students go straight from Stage 2 to Stage 4.
  4. Stage 4 (Solve on Your Own): Solve a new problem on your own against a 15-minute timer; your code is graded against a test suite. Python and TypeScript run in your browser and C# runs on our server (design problems grade in Python and TypeScript).

Equipped with a spaced-repetition review hub on a fixed 7-step schedule (1 day up to 90 days), a two-pane Studio workspace, and study notes.

Pricing, Access & Commercial Terms

  • Core Curriculum: 100% Free. No credit card required.
  • Coins: New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins.
  • AI Coach: Each AI coach question costs 1-5 coins, priced by the server according to its size.
  • BYOK (Bring Your Own Key): AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK).
  • Extras: Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1).
  • Payments & Refunds: Nothing on the site is sold for money: coins can only be earned, never bought. There are no subscriptions or charges, so there is nothing to refund.
  • Platform Operator: Hi👋WebEnterprise. Support & policies at hispeedalgo.com.
Skip to main content
Hi👋SpeedAlgo

Invariant-First Algorithmic Mastery

Arena
238Items
Theory Context•Math & Geometry
P1MediumMental model~4 min speedrun

Fast Power (Exponentiation by Squaring)

Unlocks
Binary Lifting

Pow(x, n) (LC 50)(opens leetcode.com)

Write your own version of pow(x, n) -- the function that raises a base x to an exponent n, i.e. produces x^n.

Negative exponents must work too: x^(-n) means 1 / x^n.

Example 1
Input:x = 2.00000, n = 10
Output:1024.00000
210 = 1024.

Fast Power

base x, exponent n ➔ halve exponent repeatedly ➔ O(log N) power
Spot it when: The exponent can be huge (up to 10910^9109 or more), or the answer is a repeated product 'modulo 109+710^9 + 7109+7'.
Fast Power
Python
1def my_pow(x: float, n: int) -> float:
2 """Binary Exponentiation: computes x^n by squaring.
3 Time: O(log N) | Space: O(1)
4 """
5 if n < 0:
6 x = 1.0 / x # x^-n == (1/x)^n
7 n = -n
8 
9 result = 1.0
10 curr_product = x # Holds x^(2^i) for the current bit i
11 
12 while n > 0:
13 if n % 2 == 1:
14 result *= curr_product # Bit is set: multiply this power in
15 curr_product *= curr_product # Square for the next bit
16 n //= 2 # Move to the next bit
17 
18 return result
Invariant: Before each round, result * curr_product ** n equals the original x ** n.

Write n in binary: x^13 = x^8 · x^4 · x^1, so only the powers x^1, x^2, x^4, ... are ever needed. curr_product squares once per bit, and result takes it in only when the current bit of n is 1 (n % 2 == 1). It is correct because result * curr_product ** n stays equal to the original x ** n every round, and the loop ends with n = 0. The trap is a negative n: flip first with x = 1 / x and n = -n (in Java or C++ copy n into 64 bits first, since -n overflows for -231).

See it run

Fast Power, step by step

x 2 · n -5 · result 1 · curr_product 2

x 0.5 · n 5 · result 1 · curr_product 0.5

x 0.5 · n 5 · result 1 · curr_product 0.5

x 0.5 · n 5 · result 0.5 · curr_product 0.5

x 0.5 · n 2 · result 0.5 · curr_product 0.25

x 0.5 · n 2 · result 0.5 · curr_product 0.25

x 0.5 · n 2 · result 0.5 · curr_product 0.25

x 0.5 · n 1 · result 0.5 · curr_product 0.0625

x 0.5 · n 1 · result 0.5 · curr_product 0.0625

x 0.5 · n 1 · result 0.03125 · curr_product 0.0625

x 0.5 · n 0 · result 0.03125 · curr_product 0.00390625

x 0.5 · n 0 · result 0.03125 · curr_product 0.00390625 · answer 0.03125

Each column is one round. The rows are the bit of n, curr_product at the start of the round, and result at the end of the round.

  • bit the bit of n tested in this round
  • curr the value of curr_product in this round
  • result result after it takes curr_product in
  • squared curr_product after it was squared for the next round

my_pow(2, -5). The board lists the bits of 5 from the lowest bit up, one column per round.

n < 0, so x becomes 1 / 2 = 0.5 and n becomes 5. Without the 1 / x step, the loop would compute 2 to the power 5.

Round 0: n = 5, so n % 2 = 1. curr_product = 0.5.

The bit is 1, so result = result * curr_product = 0.5.

Square: curr_product = 0.25. Halve: n = 2.

Round 1: n = 2, so n % 2 = 0. curr_product = 0.25.

The bit is 0, so result stays 0.5.

Square: curr_product = 0.0625. Halve: n = 1.

Round 2: n = 1, so n % 2 = 1. curr_product = 0.0625.

The bit is 1, so result = result * curr_product = 0.03125.

Square and halve: n = 0, so the loop stops.

Done: result = 0.03125, which is 2 to the power -5.

bit of n
round 01
round 10
round 21
curr_product
result
1 / 12
Gotchas1 of 4

Gotcha 1 of 4

  1. 1
    The trap

    Gotcha 1: Negating n without replacing x by 1 / x

    Mistake
    if n < 0:
    n = -n
    Fix
    if n < 0:
    x = 1.0 / x
    n = -n

    What happens: For a negative n, x ** n equals (1 / x) ** -n. The loop only handles n >= 0. With n = -n alone, it computes x ** -n. So my_pow(2.0, -2) returns 4.0 instead of 0.25.

    Example: x = 2.0, n = -2
    Mistake: returns 4.0Fix: returns 0.25
  2. 2

    Gotcha 2: Negating n in a 32-bit int in Java or C++

    What happens: In Java or C++, n can be -2^31, the smallest 32-bit int. Its negative, 2^31, does not fit in 32 bits. In Java, -n gives -2^31 again, and in C++ it is undefined behavior. Copy n into a 64-bit variable, such as a Java long, before n = -n.

  3. 3

    Gotcha 3: Reducing modulo MOD only at the end

    Mistake
    result *= curr_product
curr_product *= curr_product
    Fix
    result = result * curr_product % MOD
curr_product = curr_product * curr_product % MOD

    What happens: This problem has no modulus, but many counting problems ask for the answer modulo MOD, such as 10^9 + 7. Without % MOD after each multiplication, the numbers grow to many digits. In Python the answer is still correct, but every multiplication gets slower. In Java or C++, a 64-bit value overflows. Python's built-in pow(base, exp, MOD) runs the same loop and reduces after each step.

  4. 4

    Gotcha 4: Subtracting after pow(2, n, MOD) without adding MOD back

    Mistake
    return pow(2, n, MOD) - 2
    Fix
    return (pow(2, n, MOD) - 2 + MOD) % MOD

    What happens: pow(2, n, MOD) is already reduced, so it can be smaller than 2. For n = 500000003 and MOD = 10**9 + 7, it is exactly 1. Subtracting 2 then gives -1. Count Collisions of Monkeys on a Polygon (LC 2550) returns this difference, so it needs the fix. Add MOD before the final % MOD, because in Java and C++ % of a negative number stays negative.

    Example: n = 500000003, MOD = 10**9 + 7
    Mistake: returns -1Fix: returns 1000000006
Not this one if…
  • You must know which of many numbers are prime, as in Count Primes (LC 204), not the value of one huge power. See Sieve of Eratosthenes

Deep Dive

Why only about log n squarings are needed

A direct loop multiplies x by itself n times. For n = 10**9, that is a billion steps. Fast power uses the binary form of n.

Write n in binary. For 13, that is 1101, which means 13 = 8 + 4 + 1. So x^13 = x^8 * x^4 * x^1. Only the powers x^1, x^2, x^4, x^8, ... are needed, and each one is the square of the previous one.

n has about log2(n) bits. For n = 10**9, that is 30 bits, so the loop runs 30 times and not a billion times. The space is O(1): two numbers, result and curr_product.

The invariant: result * curr_product ** n stays equal to x ** n

Before each round, result * curr_product ** n equals the original x ** n. At the start, result = 1, curr_product = x and n is the input, so it holds.

Case n is odd. The round sets result to result * curr_product, then curr_product to its square, then n to n // 2. Write n = 2m + 1. Then curr_product ** n = curr_product * (curr_product 2) m. The first factor moved into result and the rest is the new curr_product ** m. So the product is unchanged.

Case n is even. Write n = 2m. Then curr_product n = (curr_product 2) ** m. Squaring and halving keeps the product the same, and result does not change.

The loop ends when n = 0. Then curr_product ** 0 is 1, so result equals the original x ** n.

Trace for my_pow(2.0, -5): the negative exponent step

n = -5 is negative, so the code sets x = 1.0 / x, which is 0.5, and n = 5. Now the loop computes 0.5 ** 5, and x ** n with the original values is 2 ** -5. These are equal.

The binary form of 5 is 101. Round 0: the bit is 1, so result = 1 * 0.5 = 0.5. Then curr_product becomes 0.25 and n becomes 2. Round 1: the bit is 0, so result stays 0.5. curr_product becomes 0.0625 and n becomes 1. Round 2: the bit is 1, so result = 0.5 * 0.0625 = 0.03125. Then n becomes 0 and the loop ends.

The answer is 0.03125, which is 2 ** -5. Without the x = 1.0 / x step, the code would compute 2 ** 5 = 32.

The Pow(x, n) (LC 50) examples work the same way. For x = 2.0 and n = 10, the result is 1024.0. For x = 2.0 and n = -2, it is 0.25.

Reuse: powers modulo a number

Many counting problems ask for the answer "modulo MOD" with MOD = 10**9 + 7. The same loop works if every multiplication is followed by % MOD: result = result * curr_product % MOD and curr_product = curr_product * curr_product % MOD. The values stay below MOD, so they stay small. Python's pow(base, exp, MOD) runs this loop.

Count Good Numbers (LC 1922) has a length up to 10^15. The answer is 5^a * 4^b for two counts a and b that sum to the length. Each power is one call of this loop. Maximize Number of Nice Divisors (LC 1808) and Count Collisions of Monkeys on a Polygon (LC 2550) also end in one power with a huge exponent.

A subtraction after the power needs one more step. pow(2, n, MOD) - 2 can be negative, because the reduced value can be smaller than 2. Add MOD back and take % MOD again.

Super Pow (LC 372) has the exponent as a list of digits. It applies the same square-and-multiply idea digit by digit.

60-Second Pitch

"A loop of n multiplications is too slow for a large n. I write n in binary and use the powers x^1, x^2, x^4, ..., each the square of the one before. curr_product squares every round. result multiplies by curr_product only when n % 2 == 1. Then n halves. The invariant is that result * curr_product ** n equals the original x ** n, so at n = 0 the result is correct. The time is O(log n) and the space is O(1). A negative n needs x = 1.0 / x and n = -n first, and in Java or C++ I widen n to 64 bits before negating. With a modulus, I reduce after every multiplication."

Common Questions

Why is the time O(log n)?

Each round halves n, so the loop runs once per bit of n. For n = 10**9, that is 30 rounds. Each round does at most two multiplications.

Why does the result stay correct when n is odd?

Write n = 2m + 1. Then curr_product ** n = curr_product * (curr_product 2) m. The first factor goes into result, and the second part is the new curr_product ** m. So result * curr_product ** n does not change.

How do you handle a negative exponent?

Use x n = (1 / x) -n. Set x = 1.0 / x and n = -n, then run the loop. In Java or C++, copy n into a 64-bit variable first, because -n overflows for -231.

How do you use it when the answer is modulo 10^9 + 7?

Apply % MOD after each multiplication to both result and curr_product. Both stay below MOD. In Python, pow(base, exp, MOD) does the same. Count Good Numbers (LC 1922) needs this with an exponent up to 10^15.

Can you write it with recursion?

Yes. Compute half = power(x, n // 2), then return half * half, times x when n is odd. The depth is about log2(n). The loop in the card uses O(1) space, so it is the better choice.

SWE Reasoning

Spot it

  • The exponent is huge (10^9 or more), so a loop of n multiplications is too slow (Pow(x, n) (LC 50)).
  • The answer is a repeated product "modulo 10^9 + 7" (Count Good Numbers (LC 1922), Count Collisions of Monkeys on a Polygon (LC 2550)).
  • A count has the form a^b for a large b (Maximize Number of Nice Divisors (LC 1808), Super Pow (LC 372)).
  • The task is a power, not a search for which numbers are prime. For prime tests, use Sieve of Eratosthenes.

The invariant, step by step

  1. result = 1, curr_product = x and n is the exponent. result * curr_product ** n equals x ** n.
  2. If n is odd, move one factor of curr_product into result.
  3. Square curr_product and halve n (integer division). The product result * curr_product ** n does not change.
  4. Each round removes one bit of n, so there are about log2(n) rounds.
  5. When n is 0, curr_product ** 0 is 1, and result equals x ** n.

Traps

  • Negating n without x = 1.0 / x. my_pow(2.0, -2) returns 4.0 instead of 0.25.
  • -n in a 32-bit int in Java or C++. For n = -231, the value 231 does not fit in 32 bits. Copy n into a 64-bit variable first.
  • Reducing modulo MOD only at the end. The numbers grow to many digits. In Python the answer stays correct but each multiplication gets slower. In Java or C++, a 64-bit value overflows.
  • Subtracting after pow(2, n, MOD). pow(2, 500000003, 10**9 + 7) - 2 is -1. Use (pow(2, n, MOD) - 2 + MOD) % MOD, which gives 1000000006.
  • Multiplying result by curr_product every round. Only the rounds with an odd n take the factor.

Practice

Canonical LeetCode:Pow(x, n) (LC 50)Count Good Numbers (LC 1922)Count Collisions of Monkeys on a Polygon (LC 2550)Maximize Number of Nice Divisors (LC 1808)Super Pow (LC 372)
Theory Context•Math & Geometry
P1MediumMental model~4 min speedrun

Fast Power (Exponentiation by Squaring)

Unlocks
Binary Lifting

Pow(x, n) (LC 50)(opens leetcode.com)

Write your own version of pow(x, n) -- the function that raises a base x to an exponent n, i.e. produces x^n.

Negative exponents must work too: x^(-n) means 1 / x^n.

Example 1
Input:x = 2.00000, n = 10
Output:1024.00000
210 = 1024.

Fast Power

base x, exponent n ➔ halve exponent repeatedly ➔ O(log N) power
Spot it when: The exponent can be huge (up to 10910^9109 or more), or the answer is a repeated product 'modulo 109+710^9 + 7109+7'.
Fast Power
Python
1def my_pow(x: float, n: int) -> float:
2 """Binary Exponentiation: computes x^n by squaring.
3 Time: O(log N) | Space: O(1)
4 """
5 if n < 0:
6 x = 1.0 / x # x^-n == (1/x)^n
7 n = -n
8 
9 result = 1.0
10 curr_product = x # Holds x^(2^i) for the current bit i
11 
12 while n > 0:
13 if n % 2 == 1:
14 result *= curr_product # Bit is set: multiply this power in
15 curr_product *= curr_product # Square for the next bit
16 n //= 2 # Move to the next bit
17 
18 return result
Invariant: Before each round, result * curr_product ** n equals the original x ** n.

Write n in binary: x^13 = x^8 · x^4 · x^1, so only the powers x^1, x^2, x^4, ... are ever needed. curr_product squares once per bit, and result takes it in only when the current bit of n is 1 (n % 2 == 1). It is correct because result * curr_product ** n stays equal to the original x ** n every round, and the loop ends with n = 0. The trap is a negative n: flip first with x = 1 / x and n = -n (in Java or C++ copy n into 64 bits first, since -n overflows for -231).

See it run

Fast Power, step by step

x 2 · n -5 · result 1 · curr_product 2

x 0.5 · n 5 · result 1 · curr_product 0.5

x 0.5 · n 5 · result 1 · curr_product 0.5

x 0.5 · n 5 · result 0.5 · curr_product 0.5

x 0.5 · n 2 · result 0.5 · curr_product 0.25

x 0.5 · n 2 · result 0.5 · curr_product 0.25

x 0.5 · n 2 · result 0.5 · curr_product 0.25

x 0.5 · n 1 · result 0.5 · curr_product 0.0625

x 0.5 · n 1 · result 0.5 · curr_product 0.0625

x 0.5 · n 1 · result 0.03125 · curr_product 0.0625

x 0.5 · n 0 · result 0.03125 · curr_product 0.00390625

x 0.5 · n 0 · result 0.03125 · curr_product 0.00390625 · answer 0.03125

Each column is one round. The rows are the bit of n, curr_product at the start of the round, and result at the end of the round.

  • bit the bit of n tested in this round
  • curr the value of curr_product in this round
  • result result after it takes curr_product in
  • squared curr_product after it was squared for the next round

my_pow(2, -5). The board lists the bits of 5 from the lowest bit up, one column per round.

n < 0, so x becomes 1 / 2 = 0.5 and n becomes 5. Without the 1 / x step, the loop would compute 2 to the power 5.

Round 0: n = 5, so n % 2 = 1. curr_product = 0.5.

The bit is 1, so result = result * curr_product = 0.5.

Square: curr_product = 0.25. Halve: n = 2.

Round 1: n = 2, so n % 2 = 0. curr_product = 0.25.

The bit is 0, so result stays 0.5.

Square: curr_product = 0.0625. Halve: n = 1.

Round 2: n = 1, so n % 2 = 1. curr_product = 0.0625.

The bit is 1, so result = result * curr_product = 0.03125.

Square and halve: n = 0, so the loop stops.

Done: result = 0.03125, which is 2 to the power -5.

bit of n
round 01
round 10
round 21
curr_product
result
1 / 12
Gotchas1 of 4

Gotcha 1 of 4

  1. 1
    The trap

    Gotcha 1: Negating n without replacing x by 1 / x

    Mistake
    if n < 0:
    n = -n
    Fix
    if n < 0:
    x = 1.0 / x
    n = -n

    What happens: For a negative n, x ** n equals (1 / x) ** -n. The loop only handles n >= 0. With n = -n alone, it computes x ** -n. So my_pow(2.0, -2) returns 4.0 instead of 0.25.

    Example: x = 2.0, n = -2
    Mistake: returns 4.0Fix: returns 0.25
  2. 2

    Gotcha 2: Negating n in a 32-bit int in Java or C++

    What happens: In Java or C++, n can be -2^31, the smallest 32-bit int. Its negative, 2^31, does not fit in 32 bits. In Java, -n gives -2^31 again, and in C++ it is undefined behavior. Copy n into a 64-bit variable, such as a Java long, before n = -n.

  3. 3

    Gotcha 3: Reducing modulo MOD only at the end

    Mistake
    result *= curr_product
curr_product *= curr_product
    Fix
    result = result * curr_product % MOD
curr_product = curr_product * curr_product % MOD

    What happens: This problem has no modulus, but many counting problems ask for the answer modulo MOD, such as 10^9 + 7. Without % MOD after each multiplication, the numbers grow to many digits. In Python the answer is still correct, but every multiplication gets slower. In Java or C++, a 64-bit value overflows. Python's built-in pow(base, exp, MOD) runs the same loop and reduces after each step.

  4. 4

    Gotcha 4: Subtracting after pow(2, n, MOD) without adding MOD back

    Mistake
    return pow(2, n, MOD) - 2
    Fix
    return (pow(2, n, MOD) - 2 + MOD) % MOD

    What happens: pow(2, n, MOD) is already reduced, so it can be smaller than 2. For n = 500000003 and MOD = 10**9 + 7, it is exactly 1. Subtracting 2 then gives -1. Count Collisions of Monkeys on a Polygon (LC 2550) returns this difference, so it needs the fix. Add MOD before the final % MOD, because in Java and C++ % of a negative number stays negative.

    Example: n = 500000003, MOD = 10**9 + 7
    Mistake: returns -1Fix: returns 1000000006
Not this one if…
  • You must know which of many numbers are prime, as in Count Primes (LC 204), not the value of one huge power. See Sieve of Eratosthenes

Deep Dive

Why only about log n squarings are needed

A direct loop multiplies x by itself n times. For n = 10**9, that is a billion steps. Fast power uses the binary form of n.

Write n in binary. For 13, that is 1101, which means 13 = 8 + 4 + 1. So x^13 = x^8 * x^4 * x^1. Only the powers x^1, x^2, x^4, x^8, ... are needed, and each one is the square of the previous one.

n has about log2(n) bits. For n = 10**9, that is 30 bits, so the loop runs 30 times and not a billion times. The space is O(1): two numbers, result and curr_product.

The invariant: result * curr_product ** n stays equal to x ** n

Before each round, result * curr_product ** n equals the original x ** n. At the start, result = 1, curr_product = x and n is the input, so it holds.

Case n is odd. The round sets result to result * curr_product, then curr_product to its square, then n to n // 2. Write n = 2m + 1. Then curr_product ** n = curr_product * (curr_product 2) m. The first factor moved into result and the rest is the new curr_product ** m. So the product is unchanged.

Case n is even. Write n = 2m. Then curr_product n = (curr_product 2) ** m. Squaring and halving keeps the product the same, and result does not change.

The loop ends when n = 0. Then curr_product ** 0 is 1, so result equals the original x ** n.

Trace for my_pow(2.0, -5): the negative exponent step

n = -5 is negative, so the code sets x = 1.0 / x, which is 0.5, and n = 5. Now the loop computes 0.5 ** 5, and x ** n with the original values is 2 ** -5. These are equal.

The binary form of 5 is 101. Round 0: the bit is 1, so result = 1 * 0.5 = 0.5. Then curr_product becomes 0.25 and n becomes 2. Round 1: the bit is 0, so result stays 0.5. curr_product becomes 0.0625 and n becomes 1. Round 2: the bit is 1, so result = 0.5 * 0.0625 = 0.03125. Then n becomes 0 and the loop ends.

The answer is 0.03125, which is 2 ** -5. Without the x = 1.0 / x step, the code would compute 2 ** 5 = 32.

The Pow(x, n) (LC 50) examples work the same way. For x = 2.0 and n = 10, the result is 1024.0. For x = 2.0 and n = -2, it is 0.25.

Reuse: powers modulo a number

Many counting problems ask for the answer "modulo MOD" with MOD = 10**9 + 7. The same loop works if every multiplication is followed by % MOD: result = result * curr_product % MOD and curr_product = curr_product * curr_product % MOD. The values stay below MOD, so they stay small. Python's pow(base, exp, MOD) runs this loop.

Count Good Numbers (LC 1922) has a length up to 10^15. The answer is 5^a * 4^b for two counts a and b that sum to the length. Each power is one call of this loop. Maximize Number of Nice Divisors (LC 1808) and Count Collisions of Monkeys on a Polygon (LC 2550) also end in one power with a huge exponent.

A subtraction after the power needs one more step. pow(2, n, MOD) - 2 can be negative, because the reduced value can be smaller than 2. Add MOD back and take % MOD again.

Super Pow (LC 372) has the exponent as a list of digits. It applies the same square-and-multiply idea digit by digit.

60-Second Pitch

"A loop of n multiplications is too slow for a large n. I write n in binary and use the powers x^1, x^2, x^4, ..., each the square of the one before. curr_product squares every round. result multiplies by curr_product only when n % 2 == 1. Then n halves. The invariant is that result * curr_product ** n equals the original x ** n, so at n = 0 the result is correct. The time is O(log n) and the space is O(1). A negative n needs x = 1.0 / x and n = -n first, and in Java or C++ I widen n to 64 bits before negating. With a modulus, I reduce after every multiplication."

Common Questions

Why is the time O(log n)?

Each round halves n, so the loop runs once per bit of n. For n = 10**9, that is 30 rounds. Each round does at most two multiplications.

Why does the result stay correct when n is odd?

Write n = 2m + 1. Then curr_product ** n = curr_product * (curr_product 2) m. The first factor goes into result, and the second part is the new curr_product ** m. So result * curr_product ** n does not change.

How do you handle a negative exponent?

Use x n = (1 / x) -n. Set x = 1.0 / x and n = -n, then run the loop. In Java or C++, copy n into a 64-bit variable first, because -n overflows for -231.

How do you use it when the answer is modulo 10^9 + 7?

Apply % MOD after each multiplication to both result and curr_product. Both stay below MOD. In Python, pow(base, exp, MOD) does the same. Count Good Numbers (LC 1922) needs this with an exponent up to 10^15.

Can you write it with recursion?

Yes. Compute half = power(x, n // 2), then return half * half, times x when n is odd. The depth is about log2(n). The loop in the card uses O(1) space, so it is the better choice.

SWE Reasoning

Spot it

  • The exponent is huge (10^9 or more), so a loop of n multiplications is too slow (Pow(x, n) (LC 50)).
  • The answer is a repeated product "modulo 10^9 + 7" (Count Good Numbers (LC 1922), Count Collisions of Monkeys on a Polygon (LC 2550)).
  • A count has the form a^b for a large b (Maximize Number of Nice Divisors (LC 1808), Super Pow (LC 372)).
  • The task is a power, not a search for which numbers are prime. For prime tests, use Sieve of Eratosthenes.

The invariant, step by step

  1. result = 1, curr_product = x and n is the exponent. result * curr_product ** n equals x ** n.
  2. If n is odd, move one factor of curr_product into result.
  3. Square curr_product and halve n (integer division). The product result * curr_product ** n does not change.
  4. Each round removes one bit of n, so there are about log2(n) rounds.
  5. When n is 0, curr_product ** 0 is 1, and result equals x ** n.

Traps

  • Negating n without x = 1.0 / x. my_pow(2.0, -2) returns 4.0 instead of 0.25.
  • -n in a 32-bit int in Java or C++. For n = -231, the value 231 does not fit in 32 bits. Copy n into a 64-bit variable first.
  • Reducing modulo MOD only at the end. The numbers grow to many digits. In Python the answer stays correct but each multiplication gets slower. In Java or C++, a 64-bit value overflows.
  • Subtracting after pow(2, n, MOD). pow(2, 500000003, 10**9 + 7) - 2 is -1. Use (pow(2, n, MOD) - 2 + MOD) % MOD, which gives 1000000006.
  • Multiplying result by curr_product every round. Only the rounds with an odd n take the factor.

Practice

Canonical LeetCode:Pow(x, n) (LC 50)Count Good Numbers (LC 1922)Count Collisions of Monkeys on a Polygon (LC 2550)Maximize Number of Nice Divisors (LC 1808)Super Pow (LC 372)
© 2026 Hi👋WebEnterprise. All rights reserved.
Sitemap•llms.txt•