Last Non-Zero Digit Of A Factorial
April 5, 2013
Today’s exercise appears from time to time on beginning-programmer message boards:
Write a program that, given n, returns the last non-zero digit of n! (factorial). For instance, 7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040, and its last non-zero digit is 4.
Your task is to write a program to find the last non-zero digit of a factorial. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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
http://comeoncodeon.wordpress.com/2009/06/20/lastnon-zero-digit-of-factorial/.
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