CODEWITHSUNDEEP
javaperformanceinteger
chipette
chipette

Reputation: 23

Trailing Zeroes of a Factorial

I'm trying to solve this coding question: Given an integer n, return the number of trailing zeroes in n!

Below is my code (codec this up using the wiki link)

    public int trailingZeroes(int n) {
        int count = 0, i = 5;
        while(i<=n){
            count+= n/i;
            i*=5;
        }
        return count;
   }

This runs for all test cases except when n = Integer.MAX_VALUE upon which I get a TLE. How can I fix this code to make it cover that test case. I have read about five articles on the net and everything seems to agree with my approach.

Much thanks.

So, I followed the long/BigInteger approach (thanks y'all):

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

Upvotes: 2

Views: 3813

Answers (7)

Milan S Kumar
Milan S Kumar

Reputation: 1

Here is my python code that could solve your problem:

    def check(n):
        j,ans=5,0
        while j<=n:
            ans=ans+n//j
            j=j*5
        return ans

Upvotes: -1

Amisha Sahu
Amisha Sahu

Reputation: 89

   /*
    [n/5]+[n/25]+[n/125]+....
    if n<25 then [n/5]
    if n<125 then [n/5]+[n/25]
    if n<625 then [n/5]+[n/25]+[n/125]
    */

#include<bits/stdc++.h>
#include<iostream>
using namespace std;

int countTrailingZeroes(int n)
{
    int res=0;                             
    for(int i=5;i<=n;i=i*5){
         res=res+n/i;
    }
    return res;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin>>n;
cout<<countTrailingZeroes(n);

return 0;
}

Output

25
6

Explanation: 25!=1.551121e+25 i.e contains 6 trailing zeroes

Upvotes: -1

rkgatram
rkgatram

Reputation: 21

public class FactorialNumberTrailingZeros {

    public static void main(String[] args) {
        System.out.println(trailingZeroes(1000020));
    }

    private static int trailingZeroes(int n) {
        int count = 0;
        while (n > 0 && (n % 10 == 0)) {
            n /= 10;
            count ++;
        }
        return count;
    }
}

Upvotes: 1

M Sach
M Sach

Reputation: 34424

public static void main(String[] args) {
    int result = findFactorialTrailingZero(100);

    System.out.println("no of trailing zeros are " + result);


}

public static int findFactorialTrailingZero(int no) {
    int zeros = no / 5;

    int zeroIncrementNo = 25;
    int zerosIncrementFactor = 1;
    int nextZeroIncrenent = 5;

    for (int i = 1;no >= zeroIncrementNo; i++) {
        zeros=zeros+zerosIncrementFactor;
        zeroIncrementNo=25*(i+1);

        if(i+1==nextZeroIncrenent){
            zerosIncrementFactor++;
            nextZeroIncrenent=nextZeroIncrenent*5;
        }

    }
    return zeros;

Upvotes: 0

laune
laune

Reputation: 31300

You cannot write a for or while loop where the loop counter is an int and the upper limit is <= Integer.MAX_VALUE.

What happens with a simple increment (counter++) is that the loop counter is set to that value, the body executes and then the counter is incremented which results in a negative number, Integer.MIN_VALUE. And then everything happens all over again.

Other weird things may happen when the loop counter is incremented in quantities > 1 or (as here) is multiplied: the int loop counter just can't hold a value > Integer.MAX_VALUE

Consider another approach for iterating over these numbers. Or handle MAX_VALUE separately.

Upvotes: 3

Dawood ibn Kareem
Dawood ibn Kareem

Reputation: 79875

Your problem is that once i gets large enough (more than Integer.MAX_INT / 5) then the line i*=5; causes i to overflow to the "wrong" value. The value in question is 5 to the 14th power, which is 6103515625, but which overflows to 1808548329.

The result of this is that the loop just keeps executing forever. i will never become a value that's not <= Integer.MAX_INT, because there's just no such int.

To avoid this, you need i to be a larger data type than an int. If you change i and count in your original code to long, this will work fine. Of course, BigInteger would also work.

Upvotes: 2

John Bollinger
John Bollinger

Reputation: 181714

As Iaune observed, your loop will never terminate when n is Integer.MAX_VALUE, because there is no int greater than that number (by definition). You should be able to restructure your loop to avoid that problem. For instance, this is the same basic approach, but flipped upside-down:

public int trailingZeroes(int n) {
    int count = 0;

    while (n > 0) {
        n /= 5;
        count += n;
    }

    return count;
}

Upvotes: 4

Related Questions