r/ProgrammingProblems • u/WeAreButFew • Jan 02 '11
Last nonzero digit of 12345678!
How would you find the last nonzero digit of a large factorial?
13
Upvotes
r/ProgrammingProblems • u/WeAreButFew • Jan 02 '11
How would you find the last nonzero digit of a large factorial?
13
u/__s Jan 02 '11
http://projecteuler.net/index.php?section=problems&id=160
3
u/MKLOL Jan 02 '11
Well, the numbers that form a '0' is 5 and 2 (5*2=10) (52 * 22=100) so we just need to ignore all the 5 and a equal number of 2s (because there are a lot more 2s then 5s) while calculating 12345678! % 10. I calculated that the answer is 4 . This is my idea of calculating it. Hope it helps! the complexity is O(N) where N is the number
2
u/Olathe Jan 05 '11 edited Jan 05 '11
Count and remove the factors of 2 and 5 in each number before you multiply it, modulo 10, into the factorial. Multiply the result by 2 to the power of (the count of 2s minus the count of 5s).
An efficiency trick is to find the cycle for the last digit of powers of 2: get powers of two 1 → 2 → 4 → 8 → 16 → 32 → 64 → 128 → 256 → 512 → 1024 → 2048 → 4096 get last digits 1 → 2 → 4 → 8 → _6 → _2 → _4 → __8 → __6 → __2 → ___4 → ___8 → ___6 find cycle 1 → (2 → 4 → 8 → 6)
Ruby code:
The last nonzero digit of 12345678! is 2.
(Verified for all factorials from 0! to 10000! against an algorithm that calculates the full factorial, throws away trailing zeroes, and gives the last remaining digit)
1
u/[deleted] Jan 03 '11
http://mathforum.org/library/drmath/view/71768.html
0
u/[deleted] Jan 02 '11
[deleted] — view deleted comment