MATH & GEOMETRY · CORE

Modular arithmetic

Do math on remainders, so numbers wrap around a fixed size and huge answers stay small enough to compute exactly.

Time O(1) per operationSpace O(1)17 practice problemsStep-through picture

The idea

Modular arithmetic is math on a clock. On a 12-hour clock, 3 hours after 11 is 2, not 14: the numbers wrap around. In code, x % m gives the remainder after dividing by m, which is where x lands on a clock with m positions.

It has two big uses. First, wrap-around: a carousel with 5 slides goes from slide 4 to slide 0 with (index + 1) % 5. Second, keeping huge numbers small: when an answer is astronomically large, problems ask for it "modulo 1000000007". You can take the remainder after every addition and multiplication, and the final remainder comes out the same.

JavaScript adds two catches. The % operator keeps the sign of the left side, so -1 % 5 is -1, not 4. And numbers are exact only up to 2^53 (about 9 × 10^15), so multiplying two numbers near 10^9 loses precision. Use ((x % m) + m) % m for negatives, and BigInt for big products.

An everyday example

Hours on a clock

A meeting starts at 10 o'clock and lasts 5 hours. You don't say it ends at 15 o'clock; you count around the clock and land on 3. If you start at 2 and go back 4 hours, you land on 10, not on -2. However many hours you add, the clock only ever shows 1 to 12, so you can always keep track with small numbers.

How the example maps to the code
In the example	In the code
The 12 positions on the clock	the modulus `MOD`
Counting forward around the clock	`addMod(a, b)`, which is `(a + b) % MOD`
Going back past 12 and landing on a real hour	`normalize(x)`, which is `((x % MOD) + MOD) % MOD`
Only ever writing down the hour, never the total	taking `% MOD` after every step

From the slow way to modular arithmetic

Start with the obvious way: compute the exact answer, then take % MOD once at the end. For the path hash, character i is multiplied by 31^i. A 20-character path needs 31^19, about 2.2 × 10^28. JavaScript numbers are exact only up to 2^53, about 9 × 10^15, so the exact answer is lost long before the end.
BigInt could hold the exact number, but it keeps growing: every character adds about 5 more bits. Each multiplication gets slower as the number gets longer, so a long string costs about O(n²) work. And the final remainder is all we wanted.
Here is the fact that saves us: a remainder of a sum depends only on the remainders of its parts, and the same holds for a product. (a + b) % m equals ((a % m) + (b % m)) % m. So we may take the remainder after every single step, and the final remainder comes out the same. Every value then stays below MOD.
Values below MOD = 1_000_000_007 add up to less than 2 × 10^9, so addMod is exact with plain numbers. But two of them multiply to almost 10^18, past 2^53, so mulMod does that one product in BigInt and converts back. normalize fixes the sign that % keeps for negative inputs. Feed each character through addMod and mulMod, keeping hash and power reduced. That loop is modular arithmetic at work.

How it works

Pick the modulus, here MOD = 1_000_000_007, a large prime commonly used in problems.
For addition, add and take the remainder: (a + b) % MOD. Two values below MOD add up to less than 2^53, so plain numbers are safe.
For multiplication, the product can pass 2^53, so multiply as BigInt and convert back: Number((BigInt(a) * BigInt(b)) % BigInt(MOD)).
For values that may be negative, normalize them with ((x % MOD) + MOD) % MOD.
Apply the remainder after every single step, never only at the end.
Example: a string hash adds charCode × 31^i for each character i, keeping hash and power reduced at every step.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…

See every step at onceThe same run, laid out side by side

Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor

const MOD = 1_000_000_007;
function addMod(a, b) {
return (a + b) % MOD;
}
function mulMod(a, b) {
return Number((BigInt(a) * BigInt(b)) % BigInt(MOD));
}
function normalize(x) {
return ((x % MOD) + MOD) % MOD;
}
function pathHash(text) {
let hash = 0;
let power = 1;
for (const ch of text) {
hash = addMod(hash, mulMod(ch.charCodeAt(0), power));
power = mulMod(power, 31);
}
return hash;
}

How fast it is

Time	`O(1) per operation`
Extra memory	`O(1)`

Each operation is one addition or multiplication and one remainder on numbers of fixed size. The hash does one of each per character, so it is O(n) for a string of length n.

Best caseO(1)
A single addMod, mulMod, or normalize call, or hashing an empty string, which returns 0 without looping.
Average caseO(n)
Hashing a string of n characters: one addMod and two mulMod calls per character, each on small numbers.
Worst caseO(n)
The same for any string of length n. Values never grow, so long strings cost no more per character than short ones.

Common mistakes

Using x % m on a negative x and expecting a positive result. In JavaScript -1 % 5 is -1. Use ((x % m) + m) % m.
Multiplying two numbers near 10^9 as plain numbers before % MOD. The product loses precision. Use BigInt for the product.
Taking the remainder only at the very end. Halfway values can overflow precision long before then.
Dividing remainders directly, like (a % m) / (b % m). Use the modular inverse instead.

When to use it

Look for these clues in a problem:

The statement says "return the answer modulo 1000000007" or another large prime.
Positions wrap around: carousels, circular buffers, days of the week, color hues.
You compute a hash of a string or path and need it to stay within a fixed range.
You need to divide under a modulus (that needs a modular inverse, using fast exponentiation).

Check yourself

Answer each one in your head first, then open it.

Why is addMod safe with plain numbers but mulMod isn't?

Two values below MOD add up to less than 2.1 × 10^9, far below 2^53. They can multiply to almost 10^18, which plain numbers can't store exactly.

What is ((-7 % 3) + 3) % 3, and why the second % 3?

It's 2. -7 % 3 is -1, adding 3 gives 2. The second % 3 matters when the first remainder is already non-negative: for 7 it turns 1 + 3 = 4 back into 1.

Why must power be reduced too, not only hash?

power grows as 31^i. Without reducing it, it passes 2^53 by the eleventh character, and every term after that is built on a wrong number.

Why do "ab" and "ba" get different hashes?

Each character is weighted by 31 to the power of its position. "ab" is 97 + 98 × 31 = 3135, and "ba" is 98 + 97 × 31 = 3105.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

0 of 17 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

#643Wrap a Carousel Index

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Write a = q1 × m + r1 and b = q2 × m + r2. Then a + b = (q1 + q2) × m + (r1 + r2): the part that is a multiple of m doesn't change the remainder, so a + b and r1 + r2 have the same remainder. Multiplying out a × b gives a multiple of m plus r1 × r2, so the same holds for products. That's why replacing a value by its remainder at any point never changes the final remainder.

pathHash keeps one promise at the top of every loop: after i characters, hash is the remainder of the exact sum of code × 31^j for those characters, and power is the remainder of 31^i. Each step adds one term and multiplies power by 31, and by the rule above, reducing both keeps the promise.

Every operation is also exact. Values stay below MOD, which is below 2^30, so addMod adds two numbers below 2^31 and never loses precision. mulMod multiplies in BigInt, which is always exact, and the remainder fits back in a plain number. The loop ends after one step per character, so the promise gives the right hash.

Going deeper

3 more ideas

Why taking remainders early gives the same answer

If two numbers have the same remainder when divided by m, their sums with any third number also share a remainder, and so do their products with any third number. So replacing a number by its remainder halfway through a calculation never changes the final remainder. That is what lets you keep every value below m.

Precision: why `BigInt` is needed for products

JavaScript numbers are 64-bit floats with 53 bits for the digits, so whole numbers above 2^53 = 9,007,199,254,740,992 can't all be stored. 999999999 * 999999999 is about 10^18, and the plain result is off in its last digits, so % MOD gives a wrong answer. Converting both to BigInt makes the product exact.

Dividing under a modulus

You can't just divide remainders. Instead, multiply by the modular inverse: the number inv with b × inv % MOD === 1. When MOD is prime, inv = b^(MOD - 2) % MOD (Fermat's little theorem), computed with fast exponentiation. So a / b becomes a × inv, all modulo MOD.

Work it by hand

Every step in a table, with why

Hash the path "/docs/api". It's long enough that power passes MOD and has to wrap around.

text = "/docs/api", MOD = 1_000_000_007

Step	`ch`	Code	`hash`	`power`	What happens	Why
1	`/`	47	47	31	`hash = 0 + 47 × 1`	`hash` starts at 0 and `power` at 1. The first character is weighted by `31^0 = 1`.
2	`d`	100	3147	961	`hash = 47 + 100 × 31`	`100 × 31 = 3100`. Every value is still far below `MOD`, so no remainder changes anything yet.
3	`o`	111	109818	29791	`hash` adds `111 × 961`	`111 × 961 = 106671`, and `power` grows to `31^3`.
4	`c`	99	3059127	923521	`hash` adds `99 × 29791`	`99 × 29791 = 2949309`. `power` is now `31^4`.
5	`s`	115	109264042	28629151	`hash` adds `115 × 923521`	`115 × 923521 = 106204915`. `power` is `31^5`, still below `MOD`.
6	`/`	47	454834132	887503681	`47 × 28629151` wraps	`47 × 28629151 = 1345570097`, which passes `MOD`. `mulMod` keeps the remainder, `345570090`.
7	`a`	97	542690587	512613922	`power` wraps	`887503681 × 31 = 27512614111` would be `31^7`. Its remainder, `512613922`, is stored instead.
8	`p`	112	955449452	891031477	`hash` adds `112 × power`	From here on every value is a remainder, but the final remainder is still the same as the exact one.
9	`i`	105	513753879	621975598	`addMod` wraps `hash`	`955449452 + 558304434` passes `MOD`, so `addMod` subtracts it once, giving `513753879`.

It returns 513753879. hash and power always stayed below MOD, and the largest product, 105 × 891031477 = 93558305085, was done in BigInt. A version with no remainders until the end first gives a wrong answer at 11 characters, "/docs/api/r".

Compared with other ways

When to pick something else

Approach	Time	Extra memory	Choose it when
Modular arithmetic	`O(n)`	`O(1)`	The answer is wanted modulo a number, or you need a hash or a wrap-around index. Reduce after every step.
Exact `BigInt`, remainder at the end	`O(n²)`	`O(n)`	You need the exact huge value itself, not just its remainder.
Plain numbers, remainder at the end	`O(n)`	`O(1)`	Only when every value provably stays below `2^53`, such as very short keys. For the path hash it is wrong from 11 characters on.

Extra memory: O(1): hash and power, each below MOD. Compare with an exact BigInt hash, which grows by about 5 bits per character.

How the steps grow

Modular arithmetic, Plain numbers, remainder at the end O(n)
Exact BigInt, remainder at the end O(n²)

About how many steps for bigger inputs
Approach	n = 10	n = 1,000	n = 1,000,000
Modular arithmetic	10	1,000	1 million
Exact `BigInt`, remainder at the end	100	1 million	1 trillion
Plain numbers, remainder at the end	10	1,000	1 million

Inputs that need care

6 tricky inputs

A negative value: -3 % MOD: JavaScript gives -3, not a remainder between 0 and MOD - 1. normalize(-3) returns 1000000004, which is the same position on the clock.
A very negative value: -3 × MOD - 5: Adding MOD once isn't enough: (x + MOD) % MOD gives -5. normalize takes % MOD first, then adds MOD, so it returns 1000000002.
A product near the limit: 999999999 × 999999999: As plain numbers the product is stored as 999999998000000000, one less than the truth, so % MOD gives 63. mulMod gives the correct 64.
An empty string: pathHash(""): The loop doesn't run and it returns 0, the same as hash's starting value.
A decimal: mulMod(1.5, 2): BigInt(1.5) throws a RangeError. Modular arithmetic is for whole numbers; round or scale the inputs first.
An emoji: "😀" and "😃": for...of gives one character each, but charCodeAt(0) reads only the first half of the pair, 55357, for both. They hash the same. Use codePointAt(0) to read the whole character.

Variations and follow-ups

Twists interviewers add

Dividing with a modular inverse

To divide by b, multiply by the number inv with b × inv % MOD === 1. Because MOD is prime, inv = b^(MOD - 2) % MOD, computed with fast exponentiation. For b = 31 that gives 129032259, and mulMod(31, 129032259) is 1.

Rolling hash

To slide a window along a string, remove the leftmost character's term and add a new one, all with modular operations. Subtracting can go negative, so wrap the result in normalize. This is the core of Rabin-Karp search.

Wrap-around indexes

A carousel moves forward with (index + 1) % length and backward with (index - 1 + length) % length. The + length is a small normalize that keeps -1 from appearing when going back from slide 0.

Two moduli

Different strings can share a hash. Computing two hashes with two different primes and comparing both makes an accidental match far less likely, at twice the cost.

In an interview

Spot it, explain it, answer follow-ups

Spot it from "return the answer modulo 10^9 + 7", "the answer may be very large", or anything circular: clocks, carousels, ring buffers, days of the week.
Say the rule out loud: "I take the remainder after every addition and multiplication, which doesn't change the final remainder. Products go through BigInt because they can pass 2^53."
Test a negative intermediate value, a product of two values near MOD, and an empty input. Those three catch the sign bug, the precision bug, and the missing base case.
The common follow-up is division, such as C(n, k) modulo a prime. Answer: multiply by the modular inverse, b^(MOD - 2), computed with fast exponentiation.

Where frontend code uses it

The same idea in real UI code

Carousels, image galleries, and tab bars move with (index + 1) % count and back with (index - 1 + count) % count, so they wrap from the last item to the first.
Color pickers wrap hues around a 360-degree circle: rotating a hue of 350 by 20 gives (350 + 20) % 360 = 10.
String hashes used for cache keys or quick comparisons in editors keep the hash small with a modulus, the same way pathHash does.
Ring buffers for logs or undo history write to position % capacity, so new entries replace the oldest ones.

Modular arithmetic

The idea

An everyday example

Hours on a clock

From the slow way to modular arithmetic

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why taking remainders early gives the same answer

Precision: why `BigInt` is needed for products

Dividing under a modulus

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Dividing with a modular inverse

Rolling hash

Wrap-around indexes

Two moduli

In an interview

Where frontend code uses it

Tuto

Hi, I'm Tuto

Give feedback

The idea

An everyday example

Hours on a clock

From the slow way to modular arithmetic

How it works

Watch it run

The code

How fast it is

Common mistakes

When to use it

Check yourself

Practice problems

easy

medium

hard

Go further

Why it works

Going deeper

Why taking remainders early gives the same answer

Precision: why BigInt is needed for products

Dividing under a modulus

Work it by hand

Compared with other ways

How the steps grow

Inputs that need care

Variations and follow-ups

Dividing with a modular inverse

Rolling hash

Wrap-around indexes

Two moduli

In an interview

Where frontend code uses it

Related algorithms

Precision: why `BigInt` is needed for products