Last Non-Zero Digit Of A Factorial
April 5, 2013
The obvious brute-force solution is to calculate n factorial, then repeatedly divide by 10 until the remainder is non-zero:
(define (factorial n)
(let loop ((n n) (f 1))
(if (zero? n) f
(loop (- n 1) (* f n)))))
(define (lnz1 n)
(let loop ((f (factorial n)))
(if (zero? (modulo f 10))
(loop (quotient f 10))
(modulo f 10))))
> (lnz1 15)
8
The problem, of course, is that n! grows very quickly, so this solution is either slow or impossible to calculate.
A common solution that does not work is to calculate the factorial in the normal way, but remove all trailing zeros at each step. For instance, 15! = 1307674368000 and the last non-zero digit is 8, but removing all trailing zeros at each step gives a last non-zero digit of 3:
(define (lnz2 n) ; doesn't work
(let loop ((i 2) (f 1))
(cond ((zero? (modulo f 10)) (loop i (/ f 10)))
((< 9 f) (loop i (modulo f 10)))
((< n i) f)
(else (loop (+ i 1) (* f i))))))
> (lnz2 15)
3
We can fix that solution with a little bit of work. Factors of 2 and 5 are special because they are the factors of 10 that we remove with the trailing zeros. Thus we remove factors of 2 and 5 from each number from 1 to n, counting them as we go, multiply the remainder of each number from 1 to n after removing factors of 2 and 5 by the accumulating product, using arithmetic modulo 10, and finally multiply by the excess 2s greater than the count of 5s, again using arithmetic modulo 10:
(define (lnz3 n)
(let loop1 ((n n) (z 1) (two 0) (five 0))
(if (zero? n)
(modulo (* z (expm 2 (- two five) 10)) 10)
(let loop2 ((m n) (two two) (five five))
(cond ((zero? (modulo m 2))
(loop2 (/ m 2) (+ two 1) five))
((zero? (modulo m 5))
(loop2 (/ m 5) two (+ five 1)))
(else (loop1 (- n 1) (* z m) two five)))))))
> (lnz3 15)
8
That works, but takes time linear in n, although at least it never overflows like lnz1; on my machine, (lnz3 1000000) takes twenty minutes. It’s also the best solution I was able to come up with on my own.
If you’re good at math, there is a very fast solution. Beni Bogosel gives this explanation at his blog, and Google points to many others that are similar. We have the formula
which can be proved by removing from (5q)! terms divisible by 5: 5, 10, 5q. Since
we obtain the recurrence L(n) ≡ 2q L(q) L(r) (mod 10), where L(n) is the last non-zero digit of n! and n = 5q + r. The calculation of L(n) descends exponentially at every step to reach small numbers for which it is easy to calculate the digit. Here’s the code:
(define (lnz4 n)
(define (p k)
(if (< k 1) 1
(vector-ref '#(6 2 4 8) (modulo k 4))))
(define (l n)
(if (< n 5) (vector-ref '#(1 1 2 6 4) n)
(let ((q (quotient n 5)) (r (remainder n 5)))
(modulo (* (p q) (l q) (l r)) 10))))
(l n))
> (lnz4 15)
8
> (lnz4 1000000)
4
That computation of (lnz4 1000000) is instantaneous. You can see the sequence L(0), L(1), … at A008904.
By the way, it is much easier to compute the number of trailing zeros than the last non-zero digit. MathWorld gives this function (A027868):
(define (z n)
(let loop ((k (ilog 5 n)) (z 0))
(if (zero? k) z
(loop (- k 1) (+ z (quotient n (expt 5 k)))))))
> (z 15)
3
> (z 1000000)
249998
I’m not sure why this is a favorite exercise for beginning programmers; I guess because it’s a fun way to introduce the modulo operator. But it’s much more of a math problem than a programming problem.
We used ilog and expm from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/KC3nkLTk.
Programming Praxis 
I came up with a linear solution where the trailing zeros are trimmed and stored only the last non-zero digit. On my computer nonZeroDigit 1000000 finishes in about 9 seconds.
nonZeroDigit :: Integral a => a -> a
nonZeroDigit x = foldr1 (\n acc -> trim (n * acc)) [1..x]
where
trim x = if x `mod` 10 > 0 then x `mod` 10 else trim (x `div` 10)
A solution in Python: http://pastebin.com/931sqKi2
lnzd = head ∘ dropWhile (≡’0′) ∘ reverse ∘ show ∘ fac
where fac n = foldr1 (*) [1‥n]
in perl6
sub lnzd1($n) {
([*] 1..$n).Str.subst(/0/,'', :g).substr(*-1)
}
sub lnzd_number(Int $n ) {
my $m = $n;
while $m %% 10 {
$m = $m div 10
}
$m;
}
sub lnzd2(Int $n) {
sub helper( Int $x , Int $acc) {
if $x == $n { lnzd_number($acc * $x) }
else { helper($x+1,lnzd_number($acc * $x) ); }
}
helper(1,1) % 10;
}
Here’s a relatively fast Haskell version based on a little number theory trickery at
With an argument of 1000000 it runs in about 0.006 seconds on a 1.7 GHz Intel Core i5.
import Control.Monad (liftM) import Data.List (genericIndex) import System.Environment (getArgs) -- Return the least significant non-zero digit of n factorial. lnzf :: Integer -> Int lnzf n | n < 5 = [1, 1, 2, 6, 4] `genericIndex` n | otherwise = let (q, r) = n `quotRem` 5 in (p q * lnzf q * lnzf r) `rem` 10 where p 0 = 1 p m = [6, 2, 4, 8] `genericIndex` (m `rem` 4) main :: IO () main = do ns <- liftM (map read) getArgs mapM_ (\n -> putStrLn $ show n ++ "! -> " ++ show (lnzf n)) ns# Ruby
def last_digit(n)
n % 10
end
def last_non_zero_digit(n)
while last_digit(n) == 0
n = n / 10
end
last_digit n
end
max = ARGV[0].to_i
puts (1..max).inject(1) { |result, n| result = last_non_zero_digit(result * n) }
But, wait, solution 2 will work with a couple changes, no?
(define (lnz2 n) ; doesn’t work
(let loop ((i 2) (f 1))
(cond ((zero? (modulo f 10)) (loop i (/ f 10)))
((< n i) (modulo f 10))
(else (loop (+ i 1) (* f i))))))
(display (lnz2 15)) (newline)
My solution in Java:
My solution in Java (link): http://pastebin.com/awgkzbb8
This is my solution done in Haskell.
–the factorial function to be used
factorial :: Int -> Int
factorial n=product [1..n]
–Done in two steps.
–Step 1.Find the last non-zero digit of a number.
lastNonZeroDigit :: Int -> Int
lastNonZeroDigit n = if n `mod` 10 /= 0
then n `mod` 10
else lastNonZeroDigit (n `quot` 10)
–Step 2.Now putting the output of factorial into the lastNonZeroDigit function input
lastNZDfactorial :: Int -> Int
lastNZDfactorial n = lastNonZeroDigit ( factorial (n))
——————————————————————————————————
This could probably have been done without two functions for the last digit but
in Haskell this way is prefered(That is what I heard).
Again the lines with the “::” can be omitted.
I am new to programming in Haskell so I would appreciate someone can tell me how to
improve this or my Haskell skills overall.
generic solution in python:
# Program to print # the last non zero digit # in a factorial def Fact(n): if n < 1: return 1 else: return n * Fact(n-1) def Convert_Num_Str(): lst_append = [] n = input("Enter the number whose factorial has to be calculated:>") result = Fact(int(n)) str_num = list(str(result)) print(str_num) for i in range(len(str_num)): if str_num[int(i)]!= '0': lst_append.append(str_num[i]) return int(lst_append[-1]) print(Convert_Num_Str())This is using simple division and loop and exit control logic
# Program to print # the last non zero digit # in a factorial def Fact(n): if n < 1: return 1 else: return n * Fact(n-1) def Convert_Num_Str(): n = input("Enter the number whose factorial has to be calculated:>") result = Fact(int(n)) while result!=0: print("Result before division", result) remainder = result%10 print(remainder) if remainder!=0: break else: result = result/10 print("Result in Else",result) remainder = result%10 print("Remainder in Else",remainder) return remainder print(Convert_Num_Str())in C++
#include
#include
#include
using namespace std;
int main()
{
int n;
cout<<"ENTER A NUMBER"<>n;
int p=0;
int fact=1;
int LastDigit=0;
while (p<n)
{
p++;
fact=fact*p;
LastDigit=fact%10;
if (LastDigit==0)
fact=fact/10;
}
cout<<""<<LastDigit<<" Is The Last Digit Of The Factorial"<<endl;
getch();
return 0;
}
C#:
static void PrintLastNonZeroDigitInFactorial(int factorial) { Console.WriteLine(IntSplitReverse(Enumerable.Range(1, factorial).Aggregate(1, (product, nextNumber) => product * nextNumber)).FirstOrDefault(d => d != 0)); } static IEnumerable<int> IntSplitReverse(int num) { List<int> digits = new List<int>(); while (num > 0) { digits.Add(num % 10); num /= 10; } return digits; }Nothing super-duper, but a Ruby solution:
def last_non_zero_fact_dig(n) fact = (1..n).inject(1){|prod, i| prod * i} (0..Math::log10(fact)).each do |k| digit = (fact / 10**k) % 10 return digit if digit != 0 end end