def power(x: int, n: int) -> int: result = 1 while n > 0: if n % 2 == 1: # (1) result *= x x *= x # (2) n //= 2 # (3) return resultprint(power(3, 5)) # → 243print(power(2, 10)) # → 1024print(power(7, 0)) # → 1
(1) If the power is odd, one copy of x goes into the answer now.
(2) Square x. If x was 3, it becomes 3^2, then 3^4, then 3^8.
(3) Halve the power, rounding down.
Trace for 3^5. The power 5 is 101 in binary, which means 5 = 4 + 1. So 3^5 = 3^4 \times 3^1.
n
odd?
result
x after squaring
5
yes
1 \times 3 = 3
9
2
no
3
81
1
yes
3 \times 81 = 243
6561
0
stop
243
The loop picks out exactly the powers 3^1, 3^2, 3^4, \dots whose binary digit in n is 1, and multiplies them together. That is why this method is also called binary exponentiation.
Cost:O(\log n) multiplications instead of O(n).
Negative powers.x^{-n} = 1 / x^n. LeetCode 50 asks for this with decimal x. Work out the power of |n|, then divide 1 by it. 4.28.6 does that version.
Python's own pow(x, n) and x ** n already use this method.
The answer is some number between 0 and n. If a guess m has m * m <= n, the answer is m or bigger. If m * m > n, the answer is smaller than m. So we can guess the middle, and throw away half of the range each time. This is binary search, which 4.11.1 covers in full.
python
def int_sqrt(n: int) -> int: lo, hi = 0, n ans = 0 while lo <= hi: mid = (lo + hi) // 2 if mid * mid <= n: # (1) ans = mid # (2) lo = mid + 1 else: hi = mid - 1 # (3) return ansprint(int_sqrt(30)) # → 5print(int_sqrt(36)) # → 6print(int_sqrt(0)) # → 0print(int_sqrt(10**12)) # → 1000000
(1) Is mid small enough? Use mid * mid, not a decimal square root. Decimals can be slightly wrong for very big numbers.
(2)mid works, so it might be the answer. Remember it, then look for a bigger one.
(3)mid is too big. Look lower.
Trace for 30:
lo
hi
mid
mid * mid
action
0
30
15
225
too big
0
14
7
49
too big
0
6
3
9
fits, ans = 3
4
6
5
25
fits, ans = 5
6
6
6
36
too big
6
5
stop, answer 5
Cost:O(\log n) steps. For 10^{12}, about 40 guesses instead of a million.
Isaac Newton described a way to improve a guess again and again. For square roots it is very simple. If g is a guess for \sqrt{n}, then the average of g and n / g is a better guess.
Why? If g is too big, then n / g is too small, and the other way round. The real root sits between them. Their average is much closer to it.
python
def int_sqrt_newton(n: int) -> int: if n < 2: return n g = n while g * g > n: g = (g + n // g) // 2 # average of g and n / g, rounded down return gprint(int_sqrt_newton(30)) # → 5print(int_sqrt_newton(10**12)) # → 1000000
Newton's method roughly doubles the number of correct digits with every step, once it gets close. It needs only a handful of steps even for huge numbers. Python's math.isqrt(n) gives the same answer and is the one to use in real code.
A number is a perfect square when its whole-number square root, squared, gives the number back.
python
from math import isqrtdef is_perfect_square(n: int) -> bool: if n < 0: return False r = isqrt(n) return r * r == nprint(is_perfect_square(49), is_perfect_square(50)) # → True False
Common mistake. People write int(n ** 0.5) ** 2 == n. The ** 0.5 uses decimals. For very large numbers, decimals are not exact, and the check can give the wrong answer. isqrt uses only whole numbers, so it is always exact.
There is also a cute fact: the odd numbers add up to the perfect squares. 1 = 1, 1 + 3 = 4, 1 + 3 + 5 = 9, 1 + 3 + 5 + 7 = 16. You can check a perfect square by subtracting 1, 3, 5, 7, … until you reach 0 or go below it. That is O(\sqrt{n}), so it is only a fun fact, not the fast way.
Some answers are huge, with thousands of digits. So many problems say: "return the answer modulo 10^9 + 7". Modulo means the remainder after dividing. In Python it is %.
You do not have to work out the huge number first. You can take the remainder after every step. These rules make that safe:
(a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m
(a \times b) \bmod m = \big((a \bmod m) \times (b \bmod m)\big) \bmod m
In plain words: after every addition or multiplication, you may take % MOD, and the final answer is the same.
python
MOD = 10**9 + 7def power_mod(x: int, n: int, m: int = MOD) -> int: result = 1 x %= m while n > 0: if n % 2 == 1: result = result * x % m # take the remainder after each multiply x = x * x % m n //= 2 return resultprint(power_mod(2, 10)) # → 1024print(power_mod(2, 1000)) # → 688423210print(pow(2, 1000, MOD)) # → 688423210
This is the fast power from part 1, with % m after each multiplication. Python's built-in pow(x, n, m) does exactly this.
Why 10^9 + 7? It is a prime number. It is just under 2^{30}. Two remainders added together still fit in a 32-bit integer. Two remainders multiplied together still fit in a 64-bit integer. So the maths never overflows in Java or C++.
Subtraction needs care. In Python, (a - b) % MOD is always 0 or more, so it is safe. In Java and C++, the % of a negative number is negative. There you write ((a - b) % MOD + MOD) % MOD.
Division is different. You cannot just divide remainders. The fix uses a trick called the modular inverse. 4.28.9 explains it step by step.
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"How many multiplications does fast power need?" About \log_2 n, because each step halves the power. For a billion, about 30.
"What about a negative power?" Work out the power of the positive number, then divide 1 by the result. Also handle x = 0 with a negative power, which has no answer.
"Find the square root without sqrt()." Binary search between 0 and n. If mid * mid <= n, remember mid and search higher. Otherwise search lower.
"Why not use n ** 0.5?" It uses decimals, which are not exact for very big numbers. math.isqrt or binary search use whole numbers and are always exact.
"Why can you take % MOD after every step?" Because the remainder of a sum or product depends only on the remainders of the parts. So taking remainders early never changes the final remainder.
One thing to volunteer: "Fast power works because every number can be written as a sum of powers of two, like 5 = 4 + 1. The loop just reads those binary digits."
Next: you have now used every basic tool these rounds ask for: digit loops, counting, swapping, two pointers, running totals, recursion, the main sorts, and these number tricks. 4.1 Complexity explains the costs you have been working out on every page. After that, Part 4 moves into the NeetCode problems, one pattern at a time.