Khuong Khuong - 1 month ago 9
Java Question

Find first non zero number in N! in Java

How to find first non zero number of the factorial of N. N can be in range from 1 to 2147483647. The output return an integer number.

EX:

findFirstNoneZeroNumberOfTheFactorial(4) = 4; // because 4! = 24
findFirstNoneZeroNumberOfTheFactorial(5) = 2; // because 5! = 120


here is my code:

import java.math.BigInteger;

public class Solution {
public static int findFirstNoneZeroNumberOfTheFactorial(int n) {
BigInteger fact = null;
for (int i = 1; i <= n; i++) {
fact = fact.multiply(BigInteger.valueOf(i));
}
String sFact = String.valueOf(fact);
for (int i = sFact.length() - 1; i >= 0; i--) {
if (sFact.charAt(i) != '0') {
int result = Character.getNumericValue(sFact.charAt(i));
return result;
}
}
return 0;
}
public static void main(String[] args){
System.out.println(Solution.findFirstNoneZeroNumberOfTheFactorial(4));
}
}


But it doesn't work!!

Answer

Your initialization is not correct.

BigInteger fact = BigInteger.ONE;

This is not optimal. If you just need the single last non-zero digit just keep track only the last non zero digit not the whole multiplied number.

let's do some math
x     x!      last-nonzero-digit(x * last-nonzero-digit)
1     1             1*1        => 1
2     2             2*1 = 2    => 2
3     6             3*2 = 6    => 6 
4     24            6*4 = 2(4) => 4
5     120           4*5 = (2)0 => 2 
6     720           2*6 = 1(2) => 2
7     5040          2*7 = 1(4) => 4

WHY DO I HAVE TO CALCULATE THE WHOLE MULTIPLICATION?

Just keep the last non zero digit.