Wrong test cases?

  • 0

    This is my code using backtracking:

    def integerBreak(n):
            def calc(n, mp, cnt):
                if n <= 1:
                    return n
                if n not in mp:
                    ret = n if cnt != 0 else 0
                    for i in xrange(1, n/2 + 1):
                        ret = max(calc(i, mp, cnt+1) * calc(n-i, mp, cnt+1), ret)
                    mp[n] = ret
                return mp[n]
            return calc(n, {}, 0)

    It is accepted.

    But when I run the code with 59 as test case, my result is 2324522934 while the expected result is 2066242608.

    I think my result is correct, as 59 == 2 + 57, the expected result should be 2 * integerBreak(57), which is 2324522934.

    Maybe my code is buggy and shouldn't pass the OJ checking, the test cases should be updated.
    Anyone who can explain this issue is welcomed, please leave a message in the disscussion :)

  • 0

    The reason you see the expected result being 2066242608 is due to overflow error in our Java solution, which returns an int with the maximum integer limit being 2147483647.

    As python does not have overflow and can represent integer as large as it needs be, your result 2324522934 is correct.

Log in to reply

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