Number of trailing zeros of N [on hold]

I am writing a method which calculates the number of trailing zeros in a factorial of a given number.

For example:

6! = 720 --> 1trailing zero

12! = 479001600 --> 2 trailing zero

Here is my code

import java.math.BigInteger;

public class TrailingZeros
{
public static void main(String args)
{
int n = 12;
System.out.println(solution(n));
}

public static int solution(int n)
{
// computing factorial
BigInteger result = BigInteger.ONE;
for (int i = 1; i <= n; i++)
{
result = result.multiply(new BigInteger(i + ""));
}

String str = String.valueOf(result);
int count = 0;
char chars = str.toCharArray();

// counting numbers of trailing zeros
for (int i = chars.length - 1; i >= 0; i--)
{
if (chars[i] != '0')
break;
count++;
}

return count;
}
}


Its working fine. But I think it is not an efficient algorithm. Please help and thank you.

this is not really the exact place for this question
– Ilan Keshet
2 days ago

perhaps this question is better suited for Code Review
– ochi
2 days ago

I'm voting to close this question as off-topic because it belongs on Code Review
– Jim Garrison
2 days ago

There is a way to do it directly without computing the actual factorial. Saw it in a question here last week.
– EJP
2 days ago

You may be able to play around with prime factors to make a more efficient algorithm.
– Purag
2 days ago

3 Answers
3

I don't see anything wrong with your current approach, per se. But we can actually count trailing zeroes using a one-liner, comparing the length of the original number string to the length of the number with trailing zeroes removed:

String input = "479001600";
int numZeroes = input.length() - input.replaceAll("0+$", "").length();
System.out.println(numZeroes);

2


Demo

I feel that the OP's version would be quicker
– Scary Wombat
2 days ago

@ScaryWombat Quicker, perhaps. Easier to read and maintain, that's another story.
– Tim Biegeleisen
2 days ago

Yeah, agree with you.
– Scary Wombat
2 days ago

Below will work even if number is long;

long

String string = "479001600";
int counter = 0;
while (counter < string.length() && string.charAt(string.length() - 1 - counter) == '0') {
counter++;
}
System.out.println(counter);

// Output will 2


Working demo

here

here

You only need to know how many time the factor 10 is in the factorial of n. 10 is a factor of two prime: 2 and 5, so the number of times 10 is multiplied is the minimum number of appearances of 2 and 5.

How about something like:

public static int solution(int n)
{
int twos = 0;
int fives = 0;
for (int i = 1; i <= n; i++)
{
twos += countFactors(i, 2);
fives += countFactors(i, 5);
}

return Math.min(twos, fives);
}

static int countFactors(int n, int fac) {
int count = 0;
while (n >= fac && (n%fac) == 0) {
n /= fac;
++count;
}
return count;
}


UPDATE:

As @david-conrad noted, the twos are much more frequent than the fives, so we only need to count the fives:

public static int solution(int n)
{
int fives = 0;
for (int i = 1; i <= n; i++)
{
fives += countFactors(i, 5);
}

return fives;
}

static int countFactors(int n, int fac) {
int count = 0;
while (n >= fac && (n%fac) == 0) {
n /= fac;
++count;
}
return count;
}


UPDATE 2: Here is a demo: http://rextester.com/DWIO77242

You will quickly discover that 2s are much more common than 5s and thus 5 is the limiting factor. The limiting reagent, in chemistry terms.
– David Conrad
2 days ago

@DavidConrad you must be right. In other words, we would only need to count the fives?
– Maurice Perry
2 days ago

That is correct.
– David Conrad
2 days ago