Skip to content

Volume ITechnology

4.0.32 — Three Number Tricks Worth Knowing: Fast Power, Square Root, Modulo ​

Classic · Medium · LeetCode 50 (Pow(x, n)), LeetCode 69 (Sqrt(x)), LeetCode 367 (Valid Perfect Square)

These three come up again and again. Each one turns a slow loop into a fast one with one simple idea.

The problem ​

  1. Work out x^n without ** or pow(), quickly, even when n is a billion.
  2. Find the whole-number square root of n without sqrt(). For 30 it is 5, because 5 \times 5 = 25 and 6 \times 6 = 36 is too big.
  3. Say whether a number is a perfect square.
  4. Learn the rules for "return the answer modulo 10^9 + 7".

1. Fast power ​

The slow way ​

Multiply x by itself n times.

python
def power_slow(x: int, n: int) -> int:
    result = 1
    for _ in range(n):
        result *= x
    return result

print(power_slow(3, 5))   # → 243

For n = one billion, that is one billion multiplications. Far too slow.

The idea: square, and halve the power ​

Look at 3^8. You do not need 8 multiplications.

  • 3^2 = 3 \times 3 = 9
  • 3^4 = 9 \times 9 = 81
  • 3^8 = 81 \times 81 = 6561

Three multiplications instead of eight. Each squaring doubles the power.

When the power is odd, take one x out first. 3^9 = 3 \times 3^8.

So the rule is:

  • if n is even, x^n = (x^2)^{n/2}
  • if n is odd, x^n = x \times x^{n-1}

Each step at least halves n. Halving a billion down to 1 takes only about 30 steps.

The solution ​

python
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 result

print(power(3, 5))      # → 243
print(power(2, 10))     # → 1024
print(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.

nodd?resultx after squaring
5yes1 \times 3 = 39
2no381
1yes3 \times 81 = 2436561
0stop243

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.

2. Whole-number square root ​

The slow way ​

Try 1, 2, 3, and so on, until the square is too big. For n = 10^{12}, that is a million tries. It works, but we can do much better.

Binary search on the answer ​

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 ans

print(int_sqrt(30))     # → 5
print(int_sqrt(36))     # → 6
print(int_sqrt(0))      # → 0
print(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:

lohimidmid * midaction
03015225too big
014749too big
0639fits, ans = 3
46525fits, ans = 5
66636too big
65stop, answer 5

Cost: O(\log n) steps. For 10^{12}, about 40 guesses instead of a million.

A faster way: Newton's method ​

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 g

print(int_sqrt_newton(30))      # → 5
print(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.

3. Is it a perfect square? ​

A number is a perfect square when its whole-number square root, squared, gives the number back.

python
from math import isqrt

def is_perfect_square(n: int) -> bool:
    if n < 0:
        return False
    r = isqrt(n)
    return r * r == n

print(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.

4. Answers modulo 10⁹ + 7 ​

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 + 7

def 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 result

print(power_mod(2, 10))          # → 1024
print(power_mod(2, 1000))        # → 688423210
print(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.

Complexity ​

TaskTime
Fast powerO(\log n)
Square root, binary searchO(\log n)
Square root, Newtona few steps, about O(\log \log n) once close
Perfect square check with isqrtO(\log n) or better

What the interviewer will push on ​

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.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet