April 5, 2013 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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)
By izidor on April 5, 2013 at 10:26 AM
A solution in Python: http://pastebin.com/931sqKi2
By David on April 5, 2013 at 4:21 PM
lnzd = head ∘ dropWhile (≡’0′) ∘ reverse ∘ show ∘ fac
where fac n = foldr1 (*) [1‥n]
By Egil on April 5, 2013 at 9:55 PM
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;
}
By swuecho on April 6, 2013 at 4:17 PM
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)) nsBy Globules on April 7, 2013 at 9:28 PM
# 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) }
By jeltz on April 8, 2013 at 10:03 PM
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)
By linesncodez on April 9, 2013 at 3:48 AM
My solution in Java:
By John on April 9, 2013 at 5:59 AM
My solution in Java (link): http://pastebin.com/awgkzbb8
By John on April 9, 2013 at 6:00 AM
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.
By Akshar on April 9, 2013 at 7:04 AM
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())By Radhakrishna Lambu on April 11, 2013 at 7:39 AM
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())By Radhakrishna Lambu on April 11, 2013 at 10:25 AM
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;
}
By HARSH DEPAL on April 15, 2013 at 4:54 PM
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; }By itsme86 on April 22, 2013 at 3:35 PM
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 endBy trojanfromnormandy on May 17, 2013 at 2:49 AM