I'm solving LeetCode #172:

Given an integer n, return the number of trailing zeroes in n!

Constraints:

• 0 <= n <= 104

My code finds the answer of n! first and then counts the number of trailing zeroes. However, running the code throws a stack overflow exception, and I can't for the life of me figure out why.

This is the code:

class Solution {
    public int trailingZeroes(int n){ 
        int fact = findFactorial(n);   // 120
        int ans = 0;
        
        // how many zeroes does fact have? 
        String ansString = Integer.toString(fact);
    
        // edge - if string is only one character long
        if (ansString.length()==1) {
          return 0;  
        } 
        
        // loop from the end counting the continuous zeroes
        for (int i= ansString.length()-1 ; i > 0; i--){
            Character cha = ansString.charAt(i);
            
            if (cha.equals('0')) {
                ans  ;
            }
            else {
                break;
            }
        }
        
        return ans;
    }
    
    public int findFactorial(int n){
        // base case
        if (n==1) return 1;
        
        // reduct towards base case
        else {
            int f = n * findFactorial(n-1);
            return f;
        }
    }

}

CodePudding user response：

The reason you get a stack overflow error, is because you use recursion when you calculate the factorial with findFactorial. Change it to use a loop instead of recursion, as shown here Find factorial of large numbers in Java. Thus your method findFactorial becomes:

BigInteger findFactorial(int n) {
    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 2; i <= n; i  )
        fact = fact.multiply(BigInteger.valueOf(i));
    return fact;
}

Then in your method that calls findFactorial change the lines:

int fact = findFactorial(n);
String ansString = Integer.toString(fact);

to

BigInteger fact = findFactorial(n);
String ansString = BigInteger.toString(fact);

CodePudding user response：

public class BigFactorial {
    public static void main(String[] args) {
        BigInteger f = BigInteger.ONE;
        int n = 120;
        for (int i = 2; i <= n; i  ) {
            f = f.multiply(BigInteger.valueOf(i));
        }
        System.out.println(n "! = " f);
        String fStr = f.toString();
        int len = fStr.length();
        for (int i = len-1; i >= 0; i--) {
            if (fStr.charAt(i) != '0') {
                System.out.println("There are " (len-1-i) " trailing zeros.");
                break;
            }
        }
    }
}