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?

Fierro

my guess is because you are surpassing the size of a double. – Doomsday

@jjnguy: Yea, that was my first guess, but then 25! is less than Java's max double. – Fierro

By the way, numZeros will return -1 for 1!, 2!, 3!, and 4!. – Maze

My guess is that because of floating-point errors, you're getting 9.999999999's when you expect 10's. I'm only surprised that it works for so long. – Maze

Admit it, you were trying to solve this: spoj.pl/problems/FCTRL. >:D – Canady

Answer 1

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.

April

Answer 2

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

Boring

I don't understand what you mean by count how many 2s and 5s are there in the product. – Fierro

@bLee: The only way to get a trailing 0 is to multiply a number divisible by 2 with a number divisible by 5. Every pair of 2 and 5 gives you another trailing 0. – Maze

2's and 5's are the only two prime factors of 10. Since you want to know the numbers of zeros, you care about whether or not your number is divisible by 10. If you know how many 2's and 5's go into your final number, you know how many times it's divisible by 10. – Motor

You are looking for the number of factors of 10 that occur in the expansion of 25! ; this can be found by determining the number of 2s and 5s in the expanded product. At least that's my understanding. The problem you'll run into if you don't follow this method is that you'll lose enough precision using a floating point number that you'll get the wrong answer. – Dover

Doh! You can do better, since clearly this only grows with each power of five. Editing to reflect now. – Boring

why are you counting the 2's anyways? you know the limiting factor is the 5's – Earlie

@dfa: not especially so; it would only perform a limited number of divisions / modulo to get the answer; Quick playing arround with notepad suggests there are only 28 factors of either 2 or 5 in 25!; so ~28 division and modulo operations against a very large number. – Dover

it's not against a very large number, its against each number in the range [1,25] – Earlie

@Jimmy: you cannot predict "how many zeros" will have the factorial of a number. The n parameter here is really n! – Nomadic

@CoderTao: only 28 divisions? are you sure? that is a number of the order of 2**28 which is a very small number compared to 25! – Nomadic

@Nomadic No, you can predict the number of zeros. Just count the number of times the factor 5 occurs in the numbers up to n to get the number of trailing zeros in n!. There will be enough factors 2, and each 5 together with a 2 gives a trailing 0. – Besides

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.

Ouellette

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");

Lananna

Answer 5

My 2 cents: avoid to work with double since they are error-prone. A better datatype in this case is BigInteger, and here there is a small method that will help you:

public class CountTrailingZeroes {

    public int countTrailingZeroes(double number) {
        return countTrailingZeroes(String.format("%.0f", number));
    }

    public int countTrailingZeroes(String number) {
        int c = 0;
        int i = number.length() - 1;

        while (number.charAt(i) == '0') {
            i--;
            c++;
        }

        return c;

    }

    @Test
    public void $128() {
        assertEquals(0, countTrailingZeroes("128"));
    }

    @Test
    public void $120() {
        assertEquals(1, countTrailingZeroes("120"));
    }

    @Test
    public void $1200() {
        assertEquals(2, countTrailingZeroes("1200"));
    }

    @Test
    public void $12000() {
        assertEquals(3, countTrailingZeroes("12000"));
    }

    @Test
    public void $120000() {
        assertEquals(4, countTrailingZeroes("120000"));
    }

    @Test
    public void $102350000() {
        assertEquals(4, countTrailingZeroes("102350000"));
    }

    @Test
    public void $1023500000() {
        assertEquals(5, countTrailingZeroes(1023500000.0));
    }
}

Nomadic

Aren't you still relying on a float/double? format("%.0f" – Yggdrasil

Answer 6

This is how I made it, but with bigger > 25 factorial the long capacity is not enough and should be used the class Biginteger, with witch I am not familiar yet:)

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner in = new Scanner(System.in);
    System.out.print("Please enter a number : ");
    long number = in.nextLong();
    long numFactorial = 1;

    for(long i = 1; i <= number; i++) {
        numFactorial *= i;
    }
    long result = 0;
    int divider = 5;
    for( divider =5; (numFactorial % divider) == 0; divider*=5) {
         result += 1;
    }

    System.out.println("Factorial of n is: " + numFactorial);
    System.out.println("The number contains " + result + " zeroes at its end.");

    in.close();

 }

}

Blanca

Answer 7

The best with logarithmic time complexity is the following:

public int trailingZeroes(int n) {
    if (n < 0)
        return -1;

    int count = 0;
    for (long i = 5; n / i >= 1; i *= 5) {
        count += n / i;
    }

    return count;
}

shamelessly copied from http://www.programcreek.com/2014/04/leetcode-factorial-trailing-zeroes-java/

Bulger

Answer 8

I had the same issue to solve in Javascript, and I solved it like:

var number = 1000010000;
var str = (number + '').split(''); //convert to string
var i = str.length - 1; // start from the right side of the array
var count = 0; //var where to leave result
for (;i>0 && str[i] === '0';i--){
    count++;
}
console.log(count) // console shows 4

This solution gives you the number of trailing zeros.

var number = 1000010000;
var str = (number + '').split(''); //convert to string
var i = str.length - 1; // start from the right side of the	array
var count = 0; //var where to leave result
for (;i>0 && str[i] === '0';i--){
	count++;
}
console.log(count)

Longwise

Answer 9

Java's doubles max out at a bit over 9 * 10 ^ 18 where as 25! is 1.5 * 10 ^ 25. If you want to be able to have factorials that high you might want to use BigInteger (similar to BigDecimal but doesn't do decimals).

Rosettarosette

You might be confusing double with long. double maxes out at somewhere around 1.8 * 10^308, but its precision isn't too good by that point. – Maze

Answer 10

I wrote this up real quick, I think it solves your problem accurately. I used the BigInteger class to avoid that cast from double to integer, which could be causing you problems. I tested it on several large numbers over 25, such as 101, which accurately returned 24 zeros.

The idea behind the method is that if you take 25! then the first calculation is 25 * 24 = 600, so you can knock two zeros off immediately and then do 6 * 23 = 138. So it calculates the factorial removing zeros as it goes.

public static int count(int number) {
    final BigInteger zero = new BigInteger("0");
    final BigInteger ten = new BigInteger("10");
    int zeroCount = 0;
    BigInteger mult = new BigInteger("1");
    while (number > 0) {
        mult = mult.multiply(new BigInteger(Integer.toString(number)));
        while (mult.mod(ten).compareTo(zero) == 0){
            mult = mult.divide(ten);
            zeroCount += 1;
        }
        number -= 1;
    }
    return zeroCount;
}

Since you said you don't care about run time at all (not that my first was particularly efficient, just slightly more so) this one just does the factorial and then counts the zeros, so it's cenceptually simpler:

public static BigInteger factorial(int number) {
    BigInteger ans = new BigInteger("1");
    while (number > 0) {
        ans = ans.multiply(new BigInteger(Integer.toString(number)));
        number -= 1;
    }
    return ans;
}

public static int countZeros(int number) {
    final BigInteger zero = new BigInteger("0");
    final BigInteger ten = new BigInteger("10");
    BigInteger fact = factorial(number);
    int zeroCount = 0;
    while (fact.mod(ten).compareTo(zero) == 0){
        fact = fact.divide(ten);
        zeroCount += 1;
    }
}

Heir