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
"Numeric literals containing a decimal point or an exponent sign yield floating point numbers."
. If you've been on stackoverflow long enough I'm sure you've seen this stackoverflow.com/questions/588004/… linked