Counting trailing zeros of numbers resulted from factorial

Question

I'm trying to count trailing zeros of numbers that are resulted from factorials (meaning that the numbers get quite large). Following code takes a number, compute the factorial of the number, and count the trailing zeros. However, when the number is about as large as 25!, numZeros don't work.

public static void main(String[] args) {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    double fact;
    int answer;
        
    try {
        int number = Integer.parseInt(br.readLine());
        fact = factorial(number);
        answer = numZeros(fact);
    }
    catch (NumberFormatException e) {
        e.printStackTrace();
    } catch (IOException e) {
        e.printStackTrace();
    }
}

public static double factorial (int num) {
    double total = 1;
    for (int i = 1; i <= num; i++) {
        total *= i;
    }
    return total;
}   

public static int numZeros (double num) {
    int count = 0;
    int last = 0;   

    while (last == 0) {
        last = (int) (num % 10);
        num = num / 10;
        count++;
    }
    
    return count-1;
}

I am not worrying about the efficiency of this code, and I know that there are multiple ways to make the efficiency of this code BETTER. What I'm trying to figure out is why the counting trailing zeros of numbers that are greater than 25! is not working.

Any ideas?

Answer 1

You only really need to know how many 2s and 5s there are in the product. If you're counting trailing zeroes, then you're actually counting "How many times does ten divide this number?". if you represent n! as q*(2^a)*(5^b) where q is not divisible by 2 or 5. Then just taking the minimum of a and b in the second expression will give you how many times 10 divides the number. Actually doing the multiplication is overkill.

Edit: Counting the twos is also overkill, so you only really need the fives.

And for some python, I think this should work:

def countFives(n):
    fives = 0   
    m = 5
    while m <= n:
        fives = fives + (n/m)
        m = m*5
    return fives

Answer 2

Your task is not to compute the factorial but the number of zeroes. A good solution uses the formula from http://en.wikipedia.org/wiki/Trailing_zeros (which you can try to prove)

def zeroes(n):
    i = 1
    result = 0
    while n >= i:
        i *= 5
        result += n/i  # (taking floor, just like Python or Java does)
    return result

Hope you can translate this to Java. This simply computes [n / 5] + [n / 25] + [n / 125] + [n / 625] + ... and stops when the divisor gets larger than n.

DON'T use BigIntegers. This is a bozosort. Such solutions require seconds of time for large numbers.

Answer 3

The double type has limited precision, so if the numbers you are working with get too big the double will be only an approximation. To work around this you can use something like BigInteger to make it work for arbitrarily large integers.

Answer 4

You can use a DecimalFormat to format big numbers. If you format your number this way you get the number in scientific notation then every number will be like 1.4567E7 this will make your work much easier. Because the number after the E - the number of characters behind the . are the number of trailing zeros I think.

I don't know if this is the exact pattern needed. You can see how to form the patterns here

DecimalFormat formater = new DecimalFormat("0.###E0");