Free Math and bits lessonsMath and bits · Stage 1 · Primes and remainders · Step 4

Remainder digit by digit

Find the remainder of a number too long to store, reading it as text. About 8 minutes.

Build the number, keep only the remainder

Suppose an ID is so long that it fits in no number type, so it arrives as a string of digits. You can still read it the way you would aloud: 1, then 12, then 123, each step being the old value times 10 plus the new digit.

And since remainders can be taken early, keep only the remainder after each step.

Each step: is the old remainder times 10, plus the digit, then reduce.

In code

r = 0
for d in digits:
    r = (r * 10 + int(d)) % m
return r

digits = "12345", m = 7 · keep only the remainder

digit

r: 1

r = (0 × 10 + 1) % 7 = 1.

Move 1 of 5

Why it's allowed

The next remainder depends only on the previous remainder, never on the full number. Two numbers that leave the same remainder now will keep leaving the same remainder after every later digit, like two clocks that show the same time and tick together.

So swapping the big number for its remainder can never change the final answer.

Times 10: must still fit: use 64-bit numbers when the modulus is large.

Quick check

m = 7. After reading "12", r = 5. The next digit is 3. What is r now?

Show the answer

4. (5 × 10 + 3) % 7 = 53 % 7 = 4, and indeed 123 % 7 = 4.

Your problem

Remainder of a huge number

You get a whole number written as a string of digits (possibly very long) and m. Return the number % m.

Example

digits = "12345", m = 7 → 4

1 ≤ length ≤ 100,000 · 1 ≤ m ≤ 10^9

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.