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
There are three distinct numeric types: integers, floating point numbers, and complex numbers.
Python String isdecimal() The isdecimal() method returns True if all characters in a string are decimal characters. If not, it returns False.
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 .
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With