## 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 ofn! (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.

Advertisements

Pages: 1 2

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.

# 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:

This is using simple division and loop and exit control logic

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#:

Nothing super-duper, but a Ruby solution: