Failing test case "1808548329"


  • 0
    E

    The following code is failing for test case - 1808548329. Can someone please help me understand why?

    public int trailingZeroes(int n) {
        int nextCount,i=5,count=0;
        nextCount = n/i;
        
        while(nextCount > 0){
            count = count + nextCount;
            if(i*5>i)        // to check for integer overflow
                i = i*5;
            else 
                break;
            nextCount = n/i;
        }
        return count;
    }

  • 0
    S

    I've had similar code as yours and also stuck on the same test case 1808548329. However my output is 452137080, which is slightly different from yours. Also had no idea why. Here's my code:

    public int trailingZeroes(int n) {
    
        int five = 5;
        int result = 0;
    
        while (n / five > 0) {
            result += n / five;
            five = five * 5;
        }
    
        return result;
    }
    

    I just check how many factors of 5, 25, 125, 625 and so on. Can't figure out why.


  • 0
    T

    I guess this might be because of the overflow, the INT_MAX = 2147483647 which is very close to 1808548329, so when five = five * 5 > 1808548329, the variable five might overflow.


  • 0

  • 0
    L

    your overflow detection code does not work because:

    5^13 = 1220703125 < 2^31 (no overflow)
    5^14 = 6103515625 > 2^32 (overflow) and
    6103515625 % 2^32 = 1808548329 > 5^13

  • 0
    O

    Just change your int five to long five, it is a overflow problem.


  • 0
    L

    You may change your code to this:
    public int trailingZeroes(int n) {

    int five = 5;
    int result = 0;
    
    while (n / five > 0) {
        result += n / five;
        if (five > INT_MAX/5) return result;
        five = five * 5;
    }
    
    return result;
    

    }


Log in to reply
 

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