Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is x%(1e9 + 7) and x%(10**9 + 7) different in Python? If yes, why?

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
like image 753
Deep Avatar asked May 07 '21 16:05

Deep


People also ask

What are the 3 types of numbers in Python?

There are three distinct numeric types: integers, floating point numbers, and complex numbers.

How do you check whether a number is decimal or not in Python?

Python String isdecimal() The isdecimal() method returns True if all characters in a string are decimal characters. If not, it returns False.

What does N 10 mean in Python?

Therefore when you see something like n //= 10 , it is using the same += / -= / *= /etc syntax that you may have seen, where it takes the current value of n and performs the operation before the equal sign with the following variable as the second argument, returning the result into n .


Video Answer


1 Answers

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.

like image 114
Acorn Avatar answered Oct 27 '22 02:10

Acorn