What is Modulo

While solving a LeetCode problem, I discovered an interesting property of Python's modulo.

This is the LeetCode question:

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10<sup>9</sup> + 7.



Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1.
Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.
Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 109 + 7, the result is 505379714.


Constraints:

1 <= n <= 105

The problem arose when I saw a concept modulo 10⁹ + 7. Since I've never encountered this concept before, I decided to do some research on it.

And here's what I've learned:

Modulo isn't just a random math requirementl it's a practical solution to a specific hardware limiation: Integer Overflow.

So what does this even mean?

In computer science, integer overflow happens when a calculation produces a result that is too large to be stored in the memory allocated for it.

For example, if you have a 32-bit integer, the maximum value you can store is 2³² - 1 (which is 4,294,967,295). If you try to store a larger value, it will overflow and wrap around to the minimum value (which is -2,147,483,648).

Think of it like an odometer on a car. If your odometer only has 6 digits, once you hit 999,999 miles and drive one more mile, it doesn't show 1,000,000—it rolls back to 000,000.

In computers, "Integer Overflow" is that exact "roll back" moment, and it happens because hardware has physical limits.

This is because the memory allocated for the integer is fixed, and if the result is too large, it will overflow and wrap around to the minimum value.

This is a problem because it can lead to incorrect results and security vulnerabilities.

Okay, but why do we even use modulo? Isn't the value inheritcally different?

So the modulo of 118505380540 is 505379714. Since the two value is obviously different, how do we consider this a same value?

In a nutshell, I found that the modular is basically a "representative" of the answer. Thus, in the context of the LeetCode question, since the purpose of the LeetCode question is to solve the problem and Algorithm iteslf, the end result may not matter as much. We can suffice by just using the representative answer instead of the actual answer.

How does it work?

In Python we can use the modulo as such:

mod = 10**9 + 7

# add two numbers
(a + b) % mod

# multiply two numbers
(a * b) % mod