Is the default code problematic?


  • 0
    S

    To get the right-bottom point, the robot needs to walk (n - 1 + m - 1) steps; therefore, to calculate the number of unique paths, we need only to decide which steps are rightward and which steps are leftward. It is essentially a combinatorial problem, and the answer of this problem is C(n + m - 2, m - 1). But it is said that n and m are at most 100; that is to say, the maximum answer could be C(198, 99), which is out of the range of 32-bit integer...


  • 0

    Yeah, the problem should instead say that the result will fit into an int. Here are the current test cases as triples of (#paths, m, n), sorted by #paths:

    (1, 1, 1)
    (1, 1, 2)
    (1, 1, 10)
    (1, 1, 100)
    (1, 2, 1)
    (1, 10, 1)
    (1, 100, 1)
    (2, 2, 2)
    (3, 2, 3)
    (4, 2, 4)
    (6, 2, 6)
    (6, 3, 3)
    (6, 6, 2)
    (7, 2, 7)
    (7, 7, 2)
    (8, 8, 2)
    (9, 2, 9)
    (10, 3, 4)
    (20, 4, 4)
    (21, 6, 3)
    (28, 3, 7)
    (28, 7, 3)
    (35, 5, 4)
    (56, 4, 6)
    (56, 6, 4)
    (57, 57, 2)
    (70, 5, 5)
    (100, 2, 100)
    (165, 4, 9)
    (210, 5, 7)
    (252, 6, 6)
    (462, 7, 6)
    (715, 5, 10)
    (792, 8, 6)
    (924, 7, 7)
    (1001, 11, 5)
    (3432, 8, 8)
    (4495, 29, 4)
    (5050, 100, 3)
    (6435, 9, 8)
    (26235, 53, 4)
    (33649, 19, 6)
    (43758, 9, 11)
    (48620, 10, 10)
    (170544, 16, 8)
    (455126, 56, 5)
    (557845, 59, 5)
    (593775, 25, 7)
    (1307504, 10, 16)
    (2869685, 49, 6)
    (4496388, 36, 7)
    (8436285, 11, 18)
    (9366819, 41, 7)
    (10518300, 25, 9)
    (45379620, 39, 8)
    (86493225, 19, 13)
    (193536720, 23, 12)
    (254186856, 27, 11)
    (548354040, 13, 23)
    (1101716330, 38, 10)
    (1916797311, 51, 9)
    

    The code I used to get those test cases (after submitting a regular accepted solution to find out the number of test cases):

    class Solution:
        def uniquePaths(self, m, n, tests=[]):
            paths = 1
            for i in range(1, m):
                paths = paths * (n - 1 + i) / i
            tests.append((paths, m, n))
            if len(tests) == 61:
                for test in sorted(tests):
                    print test
                return -1
            return paths
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.