Why does taking modulus (%) make code faster?

Question

I was solving leetcode 2466 (https://leetcode.com/problems/count-ways-to-build-good-strings/) and I had an issue when I tried to solve the problem recursively. This was the code which was giving me a TLE:

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:

        mod = 10**9 + 7

        @lru_cache(None)
        def do(n):
            if n == 0:
                return 1
            elif n < 0:
                return 0
            return do(n-one) + do(n-zero)

        
        return sum(do(x) for x in range(low, high+1))%mod

I was taking the modulus in the end because in python there is no integer overflow like C++. But, in this code my running time was quite large, hence I solved the problem iteratively.

When I came back to solve this problem recursively, I made a small change that solved the error, and restored the speed of the code:

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:

        mod = 10**9 + 7

        @lru_cache(None)
        def do(n):
            # print(f'inside: {n}')
            if n == 0:
                return 1
            elif n < 0:
                return 0
            return (do(n-one) + do(n-zero)) % mod

        
        return sum(do(x) for x in range(low, high+1))%mod

That one line at the end of the 'do' function: return (do(n-one) + do(n-zero)) % mod did the trick as opposed to: return do(n-one) + do(n-zero)

Can anyone explain why this has happened? I cannot understand why the latter code is faster particularly in python where there is no integer overflow.

Answer 1

The change you made in the recursive code by adding the line return (do(n-one) + do(n-zero)) % mod instead of return do(n-one) + do(n-zero) has effectively reduced the computation and improved the performance of your solution.

Even though Python does not have integer overflow issues like C++, the presence of the modulo operation (% mod) can still have a significant impact on the running time. The modulo operation can help keep the intermediate values within a manageable range and prevent the numbers from growing too large.

By adding the modulo operation inside the recursive function, you are reducing the magnitude of the intermediate results and keeping them within the desired range. This can help reduce the overall computation and speed up the execution time.

In contrast, without the modulo operation, the intermediate values can potentially become very large, leading to more computations and longer execution times.

Therefore, by incorporating the modulo operation in the recursive step, you are optimizing the code and avoiding unnecessary computations, resulting in improved performance.