0
$\begingroup$

I saw a few approaches of finding the last non-zero digit using recurrence relation, CRT etc. I came up with a trivial $O(1)$ approach but didn't find it anywhere so asking it here.

We can write $1\times3\times4\times6\times7\times8\times9 $ instead of $1\times2\times3\times4\times6\times7\times8\times9\times10$, and same for $11 \dots20,\ 21 \dots30$ and so on. This gives a modulo of $-2$ (mod $10$).

So we can write $n!$ as $(-2)^{\lfloor\frac{n}{10}\rfloor}$ mod $10$ and calculate the rest in hand and multiply it with our result giving us an $O(1)$ algorithm to solve the problem.

$\endgroup$
2
$\begingroup$

$2\cdot 5\cdot 10 = 100$. That multiplies the last nonzero digit by $1$, leaving it unchanged.

$12\cdot 15\cdot 20 = 3600$. That multiplies the last nonzero digit by $6$, leaving it unchanged since it's even already.

$22\cdot 25\cdot 30 = 16500$. That multiplies the last nonzero digit by $3$ and divides by $2$. Since we have powers of $2$ to give, that's the same as multiplying by $4$. It changes.

$32\cdot 35\cdot 40 = 44800$. That multiplies the last digit by $8$, and it changes.

No, your approach doesn't work. You're not accounting for the changes that come from those terms of the product you excluded, which vary in more complicated ways than the other terms.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.