Last 3 non zero digits from factorial

Question

Can someone help me with the sample code in java how to find last 3 non zero digits from big factorial? Eg 12! :- 479001600 = 16 10! :- 3628800 =288

score 1 · Answer 1 · answered Aug 28 '20 at 16:53

The following function calculates the factorial:

private static BigInteger factorial(int n) {
    return IntStream.rangeClosed(1, n)
            .mapToObj(BigInteger::valueOf)
            .collect(Collectors.reducing(BigInteger.ONE, BigInteger::multiply));
}

And this function calculates the last 3 non-zero digits:

private static BigInteger last3NonzeroDigits(BigInteger n) {
    while (n.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
        n = n.divide(BigInteger.TEN);
    }
    return n.mod(BigInteger.valueOf(1000));
}

delete trailing zeroes: while the last digit is 0 (dividable by 10, hence i % 10 = 0), divide by 10
from the resulting number, extract the (at most) last 3 digits (i % 1000)

Test:

for (int i = 1; i <= 15; i++) {
    BigInteger f = factorial(i);
    System.out.println(i+"! = "+f + " -> " + last3NonzeroDigits(f));
}

Output:

1! = 1 -> 1
2! = 2 -> 2
3! = 6 -> 6
4! = 24 -> 24
5! = 120 -> 12
6! = 720 -> 72
7! = 5040 -> 504
8! = 40320 -> 32
9! = 362880 -> 288
10! = 3628800 -> 288
11! = 39916800 -> 168
12! = 479001600 -> 16
13! = 6227020800 -> 208
14! = 87178291200 -> 912
15! = 1307674368000 -> 368

flaxel · Accepted Answer · 2020-08-28T16:30:51.243

You can map the number to a string, loop over the digits, find the last index where maximum three non-zero digits can be found and at the end you can return the index and print the last digits as your result. I have coded a little bit and write the method findLastIndex to get the index:

fun findLastIndex(num: String): Int {
    var zero = true
    var counter = 0
    val reversedNum = num.reversed()
    
    for(i in 0 until num.length){
        if(!reversedNum[i].equals('0')){
            counter++
            zero = false;
        }
        
        if((reversedNum[i].equals('0') || counter >= 3) && !zero){
            return num.length - i - 1
        }
    }
    
    return 0
}

Now you can call the method and print the last non-zero digits:

val num = 479001600
val numString = num.toString()
val index = findLastIndex(numString)
println(numString.substring(index).replace("0", ""))

You can test it in the kotlin playground. Mapping in Java should be easy to do. For the reverse method you can have a look at the following article. Or you can inverse the for loop. Hope it helps.

Last 3 non zero digits from factorial

2 Answers2