Last Non-Zero Digit of a Factorial in Java
In this tutorial, we are going to find the last non-zero digit in the n! for a given integer n.
Example 1:
Input:
int num = 4
Output:
The Last non-zero digit of a number is 4
Explanation:
If we calculate the factorial of the num = 4 then we get, (4! = 4 * 3 * 2 * 1 = 24) the final result is 24. In the result the last non-zero digit is 4. Hence it returns the output as 4.
Example 2:
Input:
int num = 6
Output:
The Last non-zero digit of a number is 2
Explanation:
If we calculate the factorial of the num = 6 then we get, (6! = 6 * 5 * 4 * 3 * 2 * 1 = 720) the final result is 720. In the result, as the last digit is zero and here we need to return the last non-zero digit. Hence it returns 2 as the output.
Example 3:
Input:
int num = 9
Output:
The Last non-zero digit of a number is 8
Explanation:
If we calculate the factorial of the num = 6 then we get, (9! = 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 362880) the final result is 362880. In the result, as the last digit is zero and here we need to return the last non-zero digit. Hence it returns 8 as the output.
Approach: Using Recursive function and Formula
Finding n! and then determining the last non-zero digit of n is a Simple Solution. Due to arithmetic overflow, this approach is ineffective for integers that are even and somewhat large.
The recursive formula shown below is the basis of getting a Better Solution:
Let D(n) be the final non-zero digit within n!
If the tens digit of n, or its second-to-last digit, is odd
D(n) = 4 * D(floorOf(n/5)) * D(The n's unit digit)
If the tens digit of n, or its second-to-last digit, is even
D(n) = 6 * D(floorOf(n/5)) * D(The n's unit digit)
An illustration of how to use the formula:
The previously mentioned simple approach, which involves computing n! first and then locating the final digit, makes it easy to discover the last non-zero digit for values smaller than 10.
D(1) = 1, D(2) = 2, D(3) = 6, D(4) = 4, D(5) = 2, D(6) = 2, D(7) = 4, D(8) = 2, and D(9) = 8.
Example 1:
n = 29 [If the Second last digit is even then]: D(29) = 6 * D(floorOf(29/5)) * D(9) = 6 * D(5) * D(9) = 6 *2 *8 = 96 The Last non-zero digit of a number is 6
Example 2:
n = 38 [Second last digit is odd]: D(33) = 4 * D(floor(38/5)) * D(8) = 4 *D(7) *2 = 4 *4 *2 = 32 The Last non-zero digit of a number is 2
Implementation:
FileName: LastDigitFactorial.java
import java.io.*; import java.util.*; public class LastDigitFactorial { // Set the values of the final non-zero digits of // all numbers from 0 to 9 static int digits[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8}; static int Last_nonzero_digit(int num) { if (num < 10) return digits[num]; // Verify to see whether tens (or second last) // digit is even or odd // If the num = 465, then num/10 = 46 and // the (num/10)%10 = 76 // Applying the above formula for both even and odd situations. if (((num / 10) % 10) % 2 == 0) return (6 * Last_nonzero_digit(num / 5) * digits[num % 10]) % 10; else return (4 * Last_nonzero_digit(num / 5) * digits[num % 10]) % 10; } // main function public static void main (String[] args) { // printing the the input System.out.println("Enter a Number:"); // Using the Scanner class Scanner sc=new Scanner(System.in); int num=sc.nextInt(); // displaying the output System.out.println("The last non-zero digit of a number is:"); // display the output and a function call System.out.println(Last_nonzero_digit(num)); } }
Output:
Enter a Number: 6 The last non-zero digit of a number is: 2
Complexity Analysis:
The time complexity for last non-zero digit factorial is O(logn) and the space complexity is given by O(logn).
General Approach:
Look at the following steps to find the last non-zero digit of factorial for a given Number.
Step-1: It is given that we have to determine the last non-zero digit for a given number in factorial. Now, if a digit contains both 2 and 5, it becomes a multiple of 10. The last digit of the number they generate is 0.
Step-2: In order to increase the number of these occurrences, we can now divide each array element into its lowest form that is divisible by 5.
Step-3: Now reduce the number of instances of each array element that is divisible by 2 by taking its minimal version. In this manner, we avoid multiplying a 2 by a 5 because the number of 2s in a multiplication result up to n is always more than the number of 5s.
Step-4: After deleting any pairs of twos and fives, multiply each integer and then only store the last digit by multiplying the result by 10.
Step-5: Now use (current_Number - 1) as a parameter to call recursively for smaller values.
Implementation:
FileName: LastDigitFactorial2.java
import java.io.*; import java.util.*; public class LastDigitFactorial2 { // A function that returns the rightmost non-zero value public static void Factorial_Last_Digit(int n, int[] res,int sum) { int num = n; // a new variable is being assigned to 'n' if (num == 1) return; // base case // Can be used to store a count of five. // modulo divide the number while (num % 5 == 0) { num /= 5; // increment the sum count of 5 sum++; } // The number is divided by // 2 to the maximum extent possible while (sum != 0 && (num & 1) == 0) { // divide the number with 2 using the right shift operator num >>= 1; // decrement the sum sum--; } /* current number multiplied by the result ( after deleting pairings ) and use modular division in order to obtain the last digit of the result's value */ res[0] = (res[0] * (num % 10)) % 10; // calling once again for (current_number -1) Factorial_Last_Digit(n - 1, res, sum); } public static int Last_nonzero_digit(int n) { // if array containing only one element int[] res = { 1 }; Factorial_Last_Digit(n, res, 0); return res[0]; } // main function public static void main(String[] args) { // printing the the input System.out.println("Enter a Number:"); // Using the Scanner class Scanner sc=new Scanner(System.in); int n=sc.nextInt(); // displaying the output System.out.println("The last non-zero digit of a number is:"); // display the output and a function call System.out.println(Last_nonzero_digit(n)); } }
Output:
Enter a Number: 9 The last non-zero digit of a number is: 8
Complexity Analysis:
The time complexity for last non-zero digit factorial is O(N) and the space complexity is given by O(1) which is constant.