Last non-zero digit of a factorial
Given a number n, find the last non-zero digit in n!.
Examples:
Input : n = 5 Output : 2 5! = 5 * 4 * 3 * 2 * 1 = 120 Last non-zero digit in 120 is 2. Input : n = 33 Output : 8
A Simple Solution is to first find n!, then find the last non-zero digit of n. This solution doesn’t work for even slightly large numbers due to arithmetic overflow.
A Better Solution is based on the below recursive formula
Let D(n) be the last non-zero digit in n! If tens digit (or second last digit) of n is odd D(n) = 4 * D(floor(n/5)) * D(Unit digit of n) If tens digit (or second last digit) of n is even D(n) = 6 * D(floor(n/5)) * D(Unit digit of n)
Illustration of the formula:
For the numbers less than 10 we can easily find the last non-zero digit by the above simple solution, i.e., first computing n!, then finding the last digit.
D(1) = 1, D(2) = 2, D(3) = 6, D(4) = 4, D(5) = 2,
D(6) = 2, D(7) = 4, D(8) = 2, D(9) = 8.
D(1) to D(9) are assumed to be precomputed. Example 1: n = 27 [Second last digit is even]: D(27) = 6 * D(floor(27/5)) * D(7) = 6 * D(5) * D(7) = 6 * 2 * 4 = 48 Last non-zero digit is 8 Example 2: n = 33 [Second last digit is odd]: D(33) = 4 * D(floor(33/5)) * D(3) = 4 * D(6) * 6 = 4 * 2 * 6 = 48 Last non-zero digit is 8
How does the above formula work?
The below explanation provides intuition behind the formula. Readers may Refer http://math.stackexchange.com/questions/130352/last-non-zero-digit-of-a-factorial for complete proof.
14! = 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 Since we are asked about last non-zero digit, we remove all 5's and equal number of 2's from factors of 14!. We get following: 14! = 14 * 13 * 12 * 11 * 2 * 9 * 8 * 7 * 6 * 3 * 2 * 1 Now we can get last non-zero digit by multiplying last digits of above factors!
In n! a number of 2’s are always more than a number of 5’s. To remove trailing 0’s, we remove 5’s and equal number of 2’s.
Let a = floor(n/5), b = n % 5. After removing an equal number of 5’s and 2’s, we can reduce the problem from n! to 2a * a! * b!
D(n) = 2a * D(a) * D(b)
Implementation:
C++
// C++ program to find last non-zero digit in n! #include<bits/stdc++.h> using namespace std; // Initialize values of last non-zero digit of // numbers from 0 to 9 int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8}; int lastNon0Digit( int n) { if (n < 10) return dig[n]; // Check whether tens (or second last) digit // is odd or even // If n = 375, So n/10 = 37 and (n/10)%10 = 7 // Applying formula for even and odd cases. if (((n/10)%10)%2 == 0) return (6*lastNon0Digit(n/5)*dig[n%10]) % 10; else return (4*lastNon0Digit(n/5)*dig[n%10]) % 10; } // Driver code int main() { int n = 14; cout << lastNon0Digit(n); return 0; } |
C
// C program to find last non-zero digit in n! #include<stdio.h> // Initialize values of last non-zero digit of // numbers from 0 to 9 int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8}; int lastNon0Digit( int n) { if (n < 10) return dig[n]; // Check whether tens (or second last) digit // is odd or even // If n = 375, So n/10 = 37 and (n/10)%10 = 7 // Applying formula for even and odd cases. if (((n/10) % 10) % 2 == 0) return (6*lastNon0Digit(n/5)*dig[n%10]) % 10; else return (4*lastNon0Digit(n/5)*dig[n%10]) % 10; } // Driver code int main() { int n = 14; printf ( "%d" ,lastNon0Digit(n)); return 0; } // This code is contributed by allwink45. |
Java
// Java program to find last // non-zero digit in n! class GFG { // Initialize values of last non-zero digit of // numbers from 0 to 9 static int dig[] = { 1 , 1 , 2 , 6 , 4 , 2 , 2 , 4 , 2 , 8 }; static int lastNon0Digit( int n) { if (n < 10 ) return dig[n]; // Check whether tens (or second last) // digit is odd or even // If n = 375, So n/10 = 37 and // (n/10)%10 = 7 Applying formula for // even and odd cases. if (((n / 10 ) % 10 ) % 2 == 0 ) return ( 6 * lastNon0Digit(n / 5 ) * dig[n % 10 ]) % 10 ; else return ( 4 * lastNon0Digit(n / 5 ) * dig[n % 10 ]) % 10 ; } // Driver code public static void main (String[] args) { int n = 14 ; System.out.print(lastNon0Digit(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to find # last non-zero digit in n! # Initialize values of # last non-zero digit of # numbers from 0 to 9 dig = [ 1 , 1 , 2 , 6 , 4 , 2 , 2 , 4 , 2 , 8 ] def lastNon0Digit(n): if (n < 10 ): return dig[n] # Check whether tens (or second last) digit # is odd or even # If n = 375, So n/10 = 37 and (n/10)%10 = 7 # Applying formula for even and odd cases. if (((n / / 10 ) % 10 ) % 2 = = 0 ): return ( 6 * lastNon0Digit(n / / 5 ) * dig[n % 10 ]) % 10 else : return ( 4 * lastNon0Digit(n / / 5 ) * dig[n % 10 ]) % 10 return 0 # driver code n = 14 print (lastNon0Digit(n)) # This code is contributed # by Anant Agarwal. |
C#
// C# program to find last // non-zero digit in n! using System; class GFG { // Initialize values of last non-zero // digit of numbers from 0 to 9 static int []dig = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8}; static int lastNon0Digit( int n) { if (n < 10) return dig[n]; // Check whether tens (or second // last) digit is odd or even // If n = 375, So n/10 = 37 and // (n/10)%10 = 7 Applying formula // for even and odd cases. if (((n / 10) % 10) % 2 == 0) return (6 * lastNon0Digit(n / 5) * dig[n % 10]) % 10; else return (4 * lastNon0Digit(n / 5) * dig[n % 10]) % 10; } // Driver code public static void Main () { int n = 14; Console.Write(lastNon0Digit(n)); } } // This code is contributed by Nitin Mittal. |
PHP
<?php // PHP program to find last // non-zero digit in n! // Initialize values of // last non-zero digit of // numbers from 0 to 9 $dig = array (1, 1, 2, 6, 4, 2, 2, 4, 2, 8); function lastNon0Digit( $n ) { global $dig ; if ( $n < 10) return $dig [ $n ]; // Check whether tens(or second // last) digit is odd or even // If n = 375, So n/10 = 37 and // (n/10)%10 = 7 // Applying formula for even // and odd cases. if ((( $n / 10) % 10) % 2 == 0) return (6 * lastNon0Digit( $n / 5) * $dig [ $n % 10]) % 10; else return (4 * lastNon0Digit( $n / 5) * $dig [ $n % 10]) % 10; } // Driver code $n = 14; echo (lastNon0Digit( $n )); // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to find // last non-zero digit in n! // Initialize values of last non-zero // digit of numbers from 0 to 9 let dig = [1, 1, 2, 6, 4, 2, 2, 4, 2, 8]; function lastNon0Digit(n) { if (n < 10) return dig[n]; // Check whether tens (or second // last) digit is odd or even // If n = 375, So n/10 = 37 and // (n/10)%10 = 7 Applying formula // for even and odd cases. if ((parseInt(n / 10, 10) % 10) % 2 == 0) return (6 * lastNon0Digit(parseInt(n / 5, 10)) * dig[n % 10]) % 10; else return (4 * lastNon0Digit(parseInt(n / 5, 10)) * dig[n % 10]) % 10; } let n = 14; document.write(lastNon0Digit(n)); </script> |
2
Time complexity: O(log n)
Space complexity: O(log n)
A Simple Solution based on recursion having worst-case Time Complexity O(nLog(n)).
Approach:-
- It is given that you have to find the last positive digit. Now a digit is made multiple of 10 if there are 2 and 5. They produce a number with last digit 0.
- Now what we can do is divide each array element into its shortest divisible form by 5 and increase count of such occurrences.
- Now divide each array element into its shortest divisible form by 2 and decrease count of such occurrences. This way we are not considering the multiplication of 2 and a 5 in our multiplication(number of 2’s present in multiplication result upto n is always more than number of 5’s).
- Multiply each number(after removing pairs of 2’s and 5’s) now and store just last digit by taking remainder by 10.
- Now call recursively for smaller numbers by (currentNumber – 1) as parameter.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Helper Function to return the rightmost non-zero digit void callMeFactorialLastDigit( int n, int result[], int sumOf5) { int number = n; // assigning to new variable. if (number == 1) return ; // base case // To store the count of times 5 can // divide the number. while (number % 5 == 0) { number /= 5; // increase count of 5 sumOf5++; } // Divide the number by // 2 as much as possible while (sumOf5 != 0 && (number & 1) == 0) { number >>= 1; // dividing the number by 2 sumOf5--; } /*multiplied result and current number(after removing pairs) and do modular division to get the last digit of the resultant number.*/ result[0] = (result[0] * (number % 10)) % 10; // calling again for (currentNumber - 1) callMeFactorialLastDigit(n - 1, result, sumOf5); } int lastNon0Digit( int n) { int result[] = { 1 }; // single element array. callMeFactorialLastDigit(n, result, 0); return result[0]; } int main() { cout << lastNon0Digit(7) << endl; cout << lastNon0Digit(12) << endl; return 0; } // This code is contributed by rameshtravel07. |
C
#include <stdio.h> // Helper Function to return the rightmost non-zero digit void callMeFactorialLastDigit( int n, int result[], int sumOf5) { int number = n; // assaigning to new variable. if (number == 1) return ; // base case // To store the count of times 5 can // divide the number. while (number % 5 == 0) { number /= 5; // increase count of 5 sumOf5++; } // Divide the number by // 2 as much as possible while (sumOf5 != 0 && (number & 1) == 0) { number >>= 1; sumOf5--; } /*multiplied result and current number(after removing pairs) and do modular division to get the last digit of the resultant number.*/ result[0] = (result[0] * (number % 10)) % 10; // calling again for (currentNumber - 1) callMeFactorialLastDigit(n - 1, result, sumOf5); } int lastNon0Digit( int n) { int result[] = { 1 }; // single element array callMeFactorialLastDigit(n, result, 0); return result[0]; } int main() { printf ( "%d\n" ,lastNon0Digit(7)); printf ( "%d" ,lastNon0Digit(12)); return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { // Helper Function to return the rightmost non-zero // digit public static void callMeFactorialLastDigit( int n, int [] result, int sumOf5) { int number = n; // assaigning to new variable. if (number == 1 ) return ; // base case // To store the count of times 5 can // divide the number. while (number % 5 == 0 ) { number /= 5 ; // increase count of 5 sumOf5++; } // Divide the number by // 2 as much as possible while (sumOf5 != 0 && (number & 1 ) == 0 ) { number >>= 1 ; // dividing the number by 2 sumOf5--; } /*multiplied result and current number(after removing pairs) and do modular division to get the last digit of the resultant number.*/ result[ 0 ] = (result[ 0 ] * (number % 10 )) % 10 ; // calling again for (currentNumber - 1) callMeFactorialLastDigit(n - 1 , result, sumOf5); } public static int lastNon0Digit( int n) { int [] result = { 1 }; // single element array. callMeFactorialLastDigit(n, result, 0 ); return result[ 0 ]; } public static void main(String[] args) { System.out.println(lastNon0Digit( 7 )); // 3040 System.out.println(lastNon0Digit( 12 )); // 479001600 } } //This code is contributed by KaaL-EL. |
Python3
# Helper Function to return the rightmost non-zero digit def callMeFactorialLastDigit(n, result, sumOf5): number = n # assaigning to new variable. if number = = 1 : return # base case # To store the count of times 5 can # divide the number. while (number % 5 = = 0 ): number = int (number / 5 ) # increase count of 5 sumOf5 + = 1 # Divide the number by # 2 as much as possible while (sumOf5 ! = 0 and (number & 1 ) = = 0 ): number >> = 1 # dividing the number by 2 sumOf5 - = 1 """multiplied result and current number(after removing pairs) and do modular division to get the last digit of the resultant number.""" result[ 0 ] = (result[ 0 ] * (number % 10 )) % 10 # calling again for (currentNumber - 1) callMeFactorialLastDigit(n - 1 , result, sumOf5) def lastNon0Digit(n): result = [ 1 ] # single element array. callMeFactorialLastDigit(n, result, 0 ) return result[ 0 ] print (lastNon0Digit( 7 )) # 3040 print (lastNon0Digit( 12 )) # 479001600 # This code is contributed by suresh07. |
C#
using System; class GFG { // Helper Function to return the rightmost non-zero // digit static void callMeFactorialLastDigit( int n, int [] result, int sumOf5) { int number = n; // assaigning to new variable. if (number == 1) return ; // base case // To store the count of times 5 can // divide the number. while (number % 5 == 0) { number /= 5; // increase count of 5 sumOf5++; } // Divide the number by // 2 as much as possible while (sumOf5 != 0 && (number & 1) == 0) { number >>= 1; // dividing the number by 2 sumOf5--; } /*multiplied result and current number(after removing pairs) and do modular division to get the last digit of the resultant number.*/ result[0] = (result[0] * (number % 10)) % 10; // calling again for (currentNumber - 1) callMeFactorialLastDigit(n - 1, result, sumOf5); } static int lastNon0Digit( int n) { int [] result = { 1 }; // single element array. callMeFactorialLastDigit(n, result, 0); return result[0]; } static void Main() { Console.WriteLine(lastNon0Digit(7)); // 3040 Console.WriteLine(lastNon0Digit(12)); // 479001600 } } // This code is contributed by mukesh07. |
Javascript
<script> // Helper Function to return the rightmost non-zero // digit function callMeFactorialLastDigit(n, result, sumOf5) { let number = n; // assaigning to new variable. if (number == 1) return ; // base case // To store the count of times 5 can // divide the number. while (number % 5 == 0) { number /= 5; // increase count of 5 sumOf5++; } // Divide the number by // 2 as much as possible while (sumOf5 != 0 && (number & 1) == 0) { number >>= 1; // dividing the number by 2 sumOf5--; } /*multiplied result and current number(after removing pairs) and do modular division to get the last digit of the resultant number.*/ result[0] = (result[0] * (number % 10)) % 10; // calling again for (currentNumber - 1) callMeFactorialLastDigit(n - 1, result, sumOf5); } function lastNon0Digit(n) { let result = [ 1 ]; // single element array. callMeFactorialLastDigit(n, result, 0); return result[0]; } document.write(lastNon0Digit(7) + "</br>" ); // 3040 document.write(lastNon0Digit(12)); // 479001600 // This code is contributed by divyeshrabadiya07 </script> |
4 6
Time complexity :- O(N)
Space complexity :- O(1)
we used single element array (int[] result = {1}) instead of integer as Java is Strictly Pass by Value!. It does not allow pass by reference for primitive data types. That’s why I used a single element array so that the recursive function can change the value of variable(result here). If we would have taken (int result = 1) then this variable remain unaffected.
Contact Us