Reputation: 43
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
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
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