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

Pages: 1 2

### 15 Responses to “Last Non-Zero Digit Of A Factorial”

1. izidor said

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) ```

2. Egil said

lnzd = head ∘ dropWhile (≡’0′) ∘ reverse ∘ show ∘ fac
where fac n = foldr1 (*) [1‥n]

3. swuecho said

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; } ```

4. Globules said

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
```
5. jeltz said

# 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.to_i
puts (1..max).inject(1) { |result, n| result = last_non_zero_digit(result * n) }

6. 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)

7. John said

My solution in Java:

8. John said

My solution in Java (link): http://pastebin.com/awgkzbb8

9. Akshar said

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.

10. 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())
```
11. 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())

```
12. HARSH DEPAL said

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;
}

13. itsme86 said

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)
{
num /= 10;
}
return digits;
}
```
14. 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
```