Where it runs
1. The problem
Some answers are huge. The number of ways to put 100 items in order has 158 digits. The number 21000 has more than 300 digits. A normal integer holds neither.
Usually nobody needs the full number. A problem says "return the answer modulo 1e9+7": give the remainder after dividing by that prime. A rolling hash of a substring works the same way: it is a big number of which you keep only the remainder. You need the remainder; the giant number it comes from never has to be stored.
The trap: compute the whole thing first and take the remainder at the end. In JavaScript, integers above 253 - 1 are stored inexactly, and no error tells you so. By the time of the final % m, the value is already wrong.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedRecognise it
Say these words and it is this pattern
- reduce a fraction to lowest terms
- list all primes up to n
- answer modulo 1e9+7
- when do two repeating intervals line up again (LCM)
Looks similar, isn't
- Bit manipulation
Both work on the number itself. That page is about the individual bits.
- Hash set / map
A set of primes still has to be built somehow. A sieve is how you build it.
- Dynamic programming (1-D)
A formula answers at once where DP fills a table. Look for a closed form first.
- Prefix sums
Prefix sums answer over values that were stored. Here the answer comes from the numbers themselves.
GCD costs O(log of the smaller value). A sieve up to 1e7 is fine, but 1e9 is not.
On LeetCode
Counting problems that say to return the answer modulo 10^9 + 7. Take the remainder after every add and multiply, and do the multiply in BigInt, since two remainders near 10^9 multiply past 2^53.
Even positions have 5 choices and odd ones 4, so the answer is 5^a times 4^b with n up to 10^15, two calls to the lesson's powMod.
Every way collides except all clockwise and all counterclockwise, so return 2^n minus 2, adding the modulus before the remainder so the result stays positive.
For each i, multiply the result by 2 to the power of i's bit length, add i and take the remainder. The result stays below 2^30, so the product stays below 2^47.
The best product is 2^p minus 1, times 2^p minus 2 raised to 2^(p-1) minus 1. That exponent passes 2^53 for large p, so keep everything in BigInt.