CODEWITHSUNDEEP
javaalgorithmmath
user8894938
user8894938

Reputation:

Avoid using BigInteger

I have this problem:

f(N) is the last five digits before the trailing zeroes in N!.

ex: 11! = 39916800, f(11) = 99168

ex: 13! = 6227020800, f(13) = 70208

Find f(N) where N is your function input.

And my Solution is:

public static String Solving(int n) {

    if (n > 10) {
        String val;
        BigInteger z = BigInteger.ONE;
        for (int i = 1; i <= n; i++) {
            z = z.multiply(BigInteger.valueOf(i));
        }
        val = String.valueOf(z);
        val = val.substring(n % 10);
        val = val.substring(0, 5);
        return val;
    } else return "";
}

How I can avoid use BigInteger?

Upvotes: 2

Views: 134

Answers (1)

Pham Trung
Pham Trung

Reputation: 11294

Edit: thanks user58697 and greybeard for excellent suggestion.

First, calculate the number of factor five in all numbers from 1 -> n,

Then remove all pair of 2 and 5,

Finally, calculate the result modulus 10^5. 

static long mod = 100000;
public static long Solving(int n) {
    int five = 0;
    for (int power5 = 5, count ; 0 < (count = n / power5) ; power5 *= 5){ 
        five += count; 
    }

    // Number of pair (2,5) is the min number between 2 and 5
    int removeFactorTwo = five;
    int removeFactorFive = five;
    long result = 1;
    for(int i = 2; i <= n; i++){
        int st = i;
        while(st % 2 == 0 && removeFactorTwo > 0){
            st /= 2;
            removeFactorTwo--;
        }
        while(st % 5 == 0 && removeFactorFive > 0){
            st /= 5;
            removeFactorFive--;
        }
        result *= st;
        // This will make sure result always <= 10^5
        result %= mod;
    }
    return result;
}

Upvotes: 2

Related Questions