Find first non zero number in N! in Java

Question

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!!

Do you mean first non-zero *digit?* – user207421 Jul 01 '15 at 03:40 — user207421, Jul 01 '15 at 03:40
Yup, find first non-zero digit from right to left. – Twitter khuong291 Jul 01 '15 at 04:51 — Twitter khuong291, Jul 01 '15 at 04:51

score 6 · Accepted Answer · answered Jun 30 '15 at 10:25

6

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.

answered Jun 30 '15 at 10:25

Uma Kanth

5,659
2
20
41

Nice!! I got it!! Thank a lot @Uma Kanth!! – Twitter khuong291 Jun 30 '15 at 10:31
@samgak True. That's much more optimial. But I don't find a repeating cycle. – Uma Kanth Jun 30 '15 at 10:54
@UmaKanth there isn't a pattern, my mistake:http://math.stackexchange.com/questions/100544/repeating-last-non-zero-digits-of-factorial – samgak Jun 30 '15 at 11:11
@UmaKanth According to your approach, We need to have accountability for the last digit of the previous number. How is that better than brute force? – FallAndLearn Nov 15 '16 at 06:57
@FallAndLearn brute force needs to calculate the whole factorial. 1000! factorial has 2568 digits in it. Which needs a lot of computational power, where as at max 9*9 has only 2 digits in it. – Uma Kanth Nov 15 '16 at 16:59
I got your point. I am facing difficulty on analysing how to implement it. – FallAndLearn Nov 15 '16 at 17:29
@FallAndLearn http://stackoverflow.com/questions/17144997/gets-last-digit-of-a-number this should help. – Uma Kanth Nov 15 '16 at 17:34

score 2 · Answer 2 · answered Jun 30 '15 at 10:12

2

You forgot to initialize your fact variable, which results in a NullPointerException.

Change

BigInteger fact = null;

to

BigInteger fact = BigInteger.ONE;

Output for System.out.println(Solution.findFirstNoneZeroNumberOfTheFactorial(4)); :

answered Jun 30 '15 at 10:12

Eran

387,369
54
702
768

score 1 · Answer 3 · answered Jun 30 '15 at 10:15

1

Instead of converting it to a String check for the module operation and if it is different from zero this is your answer, otherwise divide by 10.

public static int findFirstNoneZeroNumberOfTheFactorial(int n) {
    long fact = 1L;
    for (int i = 1; i <= n; i++) {
        fact = fact * i;
    }
    while (fact > 0) {
        long module = fact % 10;
        if (module != 0) {
            return module;
        }
        fact = fact / 10;
    }
    return -1;

}

answered Jun 30 '15 at 10:15

Davide Lorenzo MARINO

26,420
4
39
56

But this way, it doesn't work with a big number like 99! . – Twitter khuong291 Jun 30 '15 at 10:51
It is not necessary for this problem. long is big enough and it is faster and less expensive in memory – Davide Lorenzo MARINO Jun 30 '15 at 10:53
Sorry I misunderstood the question. N can be in range from 1 to 2147483647, not N! So correct, you have to use BigInteger – Davide Lorenzo MARINO Jun 30 '15 at 10:55
It is possible to replace with BigInteger rewriting % and / operators with the corresponding mod and divide methods – Davide Lorenzo MARINO Jun 30 '15 at 10:58
Anyway, tks for your answer! :) – Twitter khuong291 Jun 30 '15 at 10:58

score 1 · Answer 4 · answered Jun 30 '15 at 12:18

Is this right??

public static int number(int n) {
        int LastNoneZero = 1;
        for (int i = 1; i <= n; i++) {
            LastNoneZero *= i;
            if (LastNoneZero > 9) {
                String s = Integer.toString(LastNoneZero);
                if (s.charAt(1) == '0') {
                    LastNoneZero = Character.getNumericValue(s.charAt(0));
                } else {
                    LastNoneZero = Character.getNumericValue(s.charAt(1));
                }
            }
        }
        return LastNoneZero;
    }

Find first non zero number in N! in Java

4 Answers4