CODEWITHSUNDEEP
javaalgorithmintlong-integer
quantum
quantum

Reputation: 99

Faster program when using long instead of int

I am trying to solve the following problem:

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

I submitted the following code which was rejected as too slow:

public int trailingZeroes(int n) {
        int result = 0;
        int k = 5;

        while (k <= n){
            result += n / k;
            k *= 5;
        }

        return result;
    }

But when I changed the variable k to long, it was fast enough/

Why is it faster when I declare k as long instead of int? (I read this question which, if I understand correctly, says the opposite should happen)

Upvotes: 3

Views: 167

Answers (2)

C. K. Young
C. K. Young

Reputation: 223183

@Tunaki's comment is probably on the money. If your n is larger than Integer.MAX_VALUE / 5, then it's possible for k to reach a value greater than Integer.MAX_VALUE / 5, then after multiplying by 5, it overflows and becomes a small number again, so your program never terminates.

Whereas, if k is a long, then it doesn't matter if its value is larger than Integer.MAX_VALUE / 5; as long as it's smaller than Long.MAX_VALUE / 5 (which it's guaranteed to be, since n is an int and ints never reach values close enough), the overflow won't occur.

Upvotes: 2

arshajii
arshajii

Reputation: 129587

k could overflow, meaning you might get an infinite loop (i.e. cases where k <= n is always true, since k could wrap around to INT_MIN when multiplied by 5).

For example, consider the case where n is INT_MAX: k <= n must be true if k is an int.

If k is a long, though, then there's no potential for overflow.

Upvotes: 2

Related Questions