CODEWITHSUNDEEP
javamath
Renigunda
Renigunda

Reputation: 45

Finding the Trailing zeros in a Factorial

I needed to find the Trailing Zeros for the given number.

For smaller inputs, it is working perfectly but for longer inputs it's not working perfectly.

long input=s.nextInt();
  long mul=1;
  int count=0;
            while(input!=1 && input<1000000000)
            {
                log.debug("mul="+mul+"Input="+input+"count="+count);
                mul =mul*input;
                input--;
                while(mul%10==0)
                {
                    count++;
                    mul=mul/10;
                }
                mul=mul%100;
                //if()
            }
            System.out.println(count);
            log.debug(count);
            count=0;

For inputs 

6//Working Correct
3//Working Correct
60//Working Correct
100//Working Correct
1024//Working Correct

23456//Working Wrong
8735373//Working Wrong

Expected Output:

0
14
24
253
5861//My output is 5858
2183837//My output is 2182992

Upvotes: 1

Views: 304

Answers (3)

TheGreatContini
TheGreatContini

Reputation: 6639

First, I really like the solution provided by questioner and answerer. But that does not answer what is wrong with your code.

It took me a while to figure it out, but I think there is a very subtle mathematical assumption you are making that doesn't actually hold true. Your assumption is that you can reduce modulo 100 every iteration and nothing is lost. That assumption turns out to be false.

Reduction modulo 100 will not work in some cases. 100 = 5^2 * 2^2 . The problem is that you are losing 5s and 2s that might ultimately contribute to more 0s, which means the answer provided by your program may be less than the real answer.

For example, if at some iteration the result is 125, then after you reduce modulo 100, you get 25. If at the next iteration you multiply by a number like 72, then the result would be (25*72) = 1800 in your program, which means 2 zeros. Now step back and look at what the result would be if you multiplied 125 by 72: (125*72) = 9000. That's 3 zeros. So your program missed the 3rd zero because reducing modulo 100 turned the number 125 = 5^3 into 25 = 5^2 (i.e. it lost a multiple of 5).

If you do not follow the mathematical argument, here's what you can do to see proof that I am right: change your mod reduction by 100 to mod reduction by 1000. I bet it gets closer to the right answer. And so long as you are careful about overflows, you can even try 10000 to get even closer.

But ultimately, this solution approach is flawed because your modulo reduction will be losing multiples of 5s and 2s for high enough numbers. Conclusion: use an approach like questioner and answerer, but make sure you can prove that it works! (He already sketched the proof for you!)

Upvotes: 3

Shooter
Shooter

Reputation: 392

You are losing zeroes due to truncation of your number to mod 100. 125 will add 3 zeroes. 625 adds 4. 3125 adds 5. But you retain just 2 digits after zeroes are trimmed. (That it works for 100 and 1024 is coincident).

However, when 25 or greater powers of 5 come in, you may lose a couple of zeros as a multiple of 8 may become a multiple of 2 due to truncation of the 100s digit.

Instead of doing a mul = mul % 100, you should keep more digits depending on the number itself.

How many? Same as the highest power of 5 less than the number.

Upvotes: 3

questioner and answerer
questioner and answerer

Reputation: 680

Instead of actually computing the answer, which will take far too long and possibly overflow your integers, just check for the number of 5's in the number.

This works because the number of trailing zeroes is determined by the number of 5s. In a factorial number, there is always more factors of 2 than there are factors of 5. The number of 5 factors in the number is the number of trailing zeroes.

int answer = 0;
for (int i = 5; i <= input; i+=5) { //i starts at 5 because we do not count 0
    answer++;
}

Upvotes: -1

Related Questions