9

For an integer x, x % (10 ** 9 + 7) and x % (1e9 + 7) are giving different results after a few iterations. To reproduce this results, I am sharing my solution for LeetCode #576. Out of Boundary Paths. My solution won't pass 5 out 94 test cases if I change return ans % (10 ** 9 + 7) to return ans % (1e9 + 7) (realising this took me an hour).

Note that this solution is much longer than one-liner presented by some genius guy here. However, the same problem arises with his solution if we change % (10 ** 9 + 7) to % (1e9 + 7).

I played a bit with the python compiler and noticed that 1e9 gives a float literal. So it seems to me that this peculiarity is caused by 'weirdness' of floating point arithmetic. But I still don't understand how a zero after decimal point can cause difference. Why is this difference arising?

Without reproducing, differences can be found here : https://www.diffchecker.com/PyKQCElB

To reproduce, here's my solution :


class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        if maxMove == 0:
            return 0
        current_state = [[0 for _ in range(n)] for _ in range(m)]
        next_state = [[0 for _ in range(n)] for _ in range(m)]
        current_state[startRow][startColumn] = 1
        ans = self.count_ways(m, n, current_state)
        
        k = 1
        while k < maxMove:
            # print("CS:", current_state)
            for i in range(m):
                for j in range(n):
                    next_state[i][j] = 0
                    if i != 0:
                        next_state[i][j] += current_state[i-1][j]
                    if i!= m-1:
                         next_state[i][j] += current_state[i+1][j]
                    if j != 0:
                        next_state[i][j] += current_state[i][j-1]
                    if j != n-1:
                        next_state[i][j] += current_state[i][j+1]
            
            current_state, next_state = next_state, current_state
            ans += self.count_ways(m, n, current_state)
            
            # print("NS:", current_state)
            # print("k:{},ans:{}".format(k, int(ans % 10 ** 9 + 7)))            
            # print("k:{},ans:{}".format(k, int(ans % 1e9 + 7)))            

            k += 1
            
        # return ans % (1e9 + 7)  # This is giving incorrect results.
        return ans % (10 ** 9 + 7)  # This works fine.
        
    def count_ways(self, m, n, grid):
        ways = 0
        for i in range(m):
            for j in [0, n-1]: # Checking left and right strips of a grid.
                ways += grid[i][j]
                 
        for j in range(n):
            for i in [0, m-1]: # Checking top and bottom strips of a grid.
                ways += grid[i][j]
                
        # This will automatically add corner boxes twice.
        
        return ways

EDIT : Use this test case (arguments to findPaths, in order) :

36
5
50
15
3
1

1 Answer 1

10

But I still don't understand how a zero after decimal point can cause difference.

Where the decimal point isn't important. It's floating!

Why is this difference arising?

Because floating point numbers in Python are the usual hardware ones which means they have limited storage and precision:

>>> int(123123123123123123123.0)
123123123123123126272
#                ^^^^ different!

But integer numbers in Python have infinite storage and precision ("bignum"):

>>> int(123123123123123123123)
123123123123123123123

So:

>>> 123123123123123123123 % 10**9
123123123

>>> 123123123123123123123 % 1e9
123126272.0

In the second case both sides are converted to floating point because one of them is.

2
  • 1
    I didn't understand why int(something.0) is not something, your edit made it clear.
    – Deep
    Commented May 7, 2021 at 17:06
  • 1
    @Deep glad it helped!
    – Acorn
    Commented May 8, 2021 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.