Abhay Mohan Gupta
Abhay Mohan Gupta

Reputation: 43

How to reduce the running time for finding the last non-zero digit of factorial of a number?

I got a question in which I have to find the last non-zero digit of factorial of a number.I used same code for java and C but it takes different time in both.

int lastDigitDiffZero(long n) {

     int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
     int i=(int) n;

     if (n < 10)
       return dig[i]; 

     if (((n/10)%10)%2 == 0)
       return (6*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10;
     else
       return (4*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10;
}

I want to know why does it takes different time and what should I do to reduce the running time?

Upvotes: 1

Views: 1051

Answers (2)

IDK
IDK

Reputation: 445

Can't you just:

private static int lastDigitDiffZero(long n)
{
   int temp = (int) n;
   int mod = temp%10;

  return (mod == 0 ? lastDigitDiffZero(temp/10) : mod);
}

Upvotes: 0

BluEOS
BluEOS

Reputation: 606

Please find the optimized version :

private static final int DIG[] = { 1, 1, 2, 6, 4, 2, 2, 4, 2, 8 };

static int lastDigitDiffZero(long n) {
        if (n < 10)
            return DIG[(int) n];
        int t1 = (int) (n % 10);
        int t2 = lastDigitDiffZero(n / 5) * DIG[t1];
        if (((n / 10) % 10) % 2 == 0) {
            return (6 * t2) % 10;
        } else
            return (4 * t2) % 10;
}

Upvotes: 1

Related Questions