Issue with large number

Question

I'm trying to count the number of trailing zero with a factorial.

e.g

4! = 24 So you retrieve 0.

9! = 362880 So you retrieve 1.

10! = 9! x 10 = 3628800 So you retrieve 2.

11! = 10! x 11 = 3.99168E7 So you retrieve 2.

    static double factorial(double n) {
        double f = 1;
        for(int i = 1 ; i <= n ; i++) {
            f *= i;
        }
        return f;
    }

    static int numberOfZeros(double f) {
        int ten = 1;
        int count = 0;
        for(;f%Math.pow(10, ten) == 0;count++) {

            ten++;
        }
        return count;
    }

this codes are Okay until number n is 22. but when i try to put 23 into then count is 0. Of course, mathematically 23! has trailing zeros.

WJS · Answer 1 · 2020-03-16T23:03:34.543

7

You don't need to calculate the factorial to count trailing zeroes.

Just see how many times you can divide by powers of 5 (which is the larger factor of 10). This works since any number with a trailing zero will be divisible by 10. You need to do the powers of 5 to catch those times when 5 occurs more than once.

for 45! = 45/25 = 1 + 45/5 = 9 = 10 zeroes.
for 150! = 150/125 = 1 150/25 = 6, 150/5 = 30 so 1 + 6 + 30 = 37 zeros.

Now all you have to do is code it.

edited Mar 16 '20 at 23:03

answered Mar 16 '20 at 22:50

WJS

36,363
4
24
39

2

Instead of dividing by 125 (5³), just keep dividing by 5, using `int` math, until you reach 0. E.g. `150 / 5 = 30` (add 30 to total), `30 / 5 = 6` (add 6 to total), `6 / 5 = 1` (add 1 to total), and done since `1 < 5`. Result: `total = 30 + 6 + 1 = 37` – Andreas Mar 17 '20 at 00:28

score 0 · Answer 2 · answered Mar 16 '20 at 22:59

0

The reason your code isn't working is that a double type can only hold 64 bits. Let's do the calculation:

A bit has two possible values, so 2^64 is the largest number a double could hold... if we aren't accounting for negative numbers. Of course, Java doubles support negative values, so we divide 2^64 (18,446,744,073,709,551,616) by two, and then subtract 1 (Because Java takes one number from the positive range to store zero). As a result, we get 9,223,372,036,854,775,807, which represents the positive bound for the Java double type, or in other words, the biggest positive number a double can store.

Now, 23 factorial is a very big number:
25,852,016,738,884,976,640,000

9,223,372,036,854,775,807
Above is the range for a double. Just by looking at the widths of the numbers, we can see that 23! exceeds the range for a double. Therefore, your double value will overflow and you won't get the right answer.

You should consider using the BigInteger class to handle such large numbers and ensure you are getting accurate answers.

GeeksForGeeks BigInteger tutorial
Java API documentation for BigInteger

answered Mar 16 '20 at 22:59

Jaeheon Shim

491
5
14

You don't need `BigInteger` because it isn't necessary to calculate the value. – WJS Mar 16 '20 at 23:05
3

That's true, I was trying to provide a way where they could refactor their current code without changing the underlying concept. – Jaeheon Shim Mar 16 '20 at 23:08
A double has 64 bits, but only 53 bits of mantissa. But, as @WJS says, there's no need to calculate the full value, only the number of factors of 5 it contains. (There will always be more 2's than 5's, so 5 is the 'limiting reagent,' as a chemist would say.) – David Conrad Mar 16 '20 at 23:09
@DavidConrad Ah yes, I was thinking about the long type. However, what would be the use of using a double here? Since we are dealing with positive integer factorials isn't it impossible to obtain a floating-point value? – Jaeheon Shim Mar 16 '20 at 23:13
You're right. But OP is using a double because Math.pow takes and returns doubles. – David Conrad Mar 16 '20 at 23:15

Issue with large number

2 Answers2

Linked