Given a number N, the task is to find the unit and tens places digit of the first N natural numbers factorials, i.e last two digit of 1!+2!+3!+….N! where N<=10e18.
Examples:
Input: n = 2
Output: 3
Explanation: 1! + 2! = 3, Last two digits are 3Input: 4
Output: 33
Explanation: 1!+2!+3!+4!=33, Last two digits are 33
Naive Approach: In this approach, simply calculate the factorial of each number and find the sum of these. Finally, get the unit and tens place the digit of the sum. This will take a lot of time and unnecessary calculations.
Efficient Approach: In this approach, only unit’s and ten’s digit of N is to be calculated in the range [1, 10], because:
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8!=40320
9!=362880
10!=3628800
so on.
As 10 != 3628800, and factorial of number greater than 10 have two trailing zeros. So, N>=10 doesn’t contribute in unit and tens place while doing sum.
Therefore,
if (n < 10)
ans = (1 ! + 2 ! +..+ n !) % 100;
else
ans = (1 ! + 2 ! + 3 ! + 4 !+ 5 ! + 6 ! + 7 ! + 8 ! + 9 ! + 10 !) % 100;
Note: We know (1! + 2! + 3! + 4!+…+10!) % 100 = 13
So we always return 13 when n is greater than 9.
Below is the implementation of the above approach.
C++
// C++ program to find the unit place digit// of the first N natural numbers factorials#include <iostream>using namespace std;#define ll long int// Function to find the unit's and ten's place digitint get_last_two_digit(long long int N){ // Let us write for cases when // N is smaller than or equal // to 10. if (N <= 10) { ll ans = 0, fac = 1; for (int i = 1; i <= N; i++) { fac = fac * i; ans += fac; } return ans % 100; } // We know following // (1! + 2! + 3! + 4!...+10!) % 100 = 13 else // (N >= 10) return 13;}// Driver codeint main(){ long long int N = 1; for (N = 1; N <= 10; N++) cout << "For N = " << N << " : " << get_last_two_digit(N) << endl; return 0;} |
Java
//Java program to find the unit place digit//of the first N natural numbers factorialspublic class AAA { //Function to find the unit's and ten's place digit static int get_last_two_digit(long N) { // Let us write for cases when // N is smaller than or equal // to 10. if (N <= 10) { long ans = 0, fac = 1; for (int i = 1; i <= N; i++) { fac = fac * i; ans += fac; } return (int)ans % 100; } // We know following // (1! + 2! + 3! + 4!...+10!) % 100 = 13 else // (N >= 10) return 13; } //Driver code public static void main(String[] args) { long N = 1; for (N = 1; N <= 10; N++) System.out.println( "For N = " + N + " : " + get_last_two_digit(N)); }} |
Python3
# Python3 program to find the unit # place digit of the first N natural# numbers factorials# Function to find the unit's# and ten's place digitdef get_last_two_digit(N): # Let us write for cases when # N is smaller than or equal # to 10 if N <= 10: ans = 0 fac = 1 for i in range(1, N + 1): fac = fac * i ans += fac ans = ans % 100 return ans # We know following # (1! + 2! + 3! + 4!...+10!) % 100 = 13 # // (N >= 10) else: return 13# Driver CodeN = 1for N in range(1, 11): print("For N = ", N, ": ", get_last_two_digit(N), sep = ' ')# This code is contributed # by sahilshelangia |
C#
// C# program to find the unit // place digit of the first N// natural numbers factorialsusing System;class GFG{// Function to find the unit's // and ten's place digitstatic int get_last_two_digit(long N){// Let us write for cases when// N is smaller than or equal// to 10.if (N <= 10){ long ans = 0, fac = 1; for (int i = 1; i <= N; i++) { fac = fac * i; ans += fac; } return (int)ans % 100;}// We know following// (1! + 2! + 3! + 4!...+10!) % 100 = 13else // (N >= 10) return 13;}// Driver codepublic static void Main() { long N = 1; for (N = 1; N <= 10; N++) Console.WriteLine( "For N = " + N + " : " + get_last_two_digit(N));}}// This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php// PHP program to find the unit place digit// of the first N natural numbers factorials// Function to find the unit's// and ten's place digitfunction get_last_two_digit($N){ // Let us write for cases when // N is smaller than or equal // to 10. if ($N <= 10) { $ans = 0; $fac = 1; for ($i = 1; $i <= $N; $i++) { $fac = $fac * $i; $ans += $fac; } return $ans % 100; } // We know following // (1! + 2! + 3! + 4!...+10!) % 100 = 13 else // (N >= 10) return 13;}// Driver code$N = 1;for ($N = 1; $N <= 10; $N++) echo "For N = " . $N . " : " . get_last_two_digit($N) . "\n";// This code is contributed // by Akanksha Rai(Abby_akku) |
Javascript
<script>// Javascript program to find the unit place digit// of the first N natural numbers factorials// Function to find the unit's and ten's place digitfunction get_last_two_digit(N){ // Let us write for cases when // N is smaller than or equal // to 10. if (N <= 10) { let ans = 0, fac = 1; for (let i = 1; i <= N; i++) { fac = fac * i; ans += fac; } return ans % 100; } // We know following // (1! + 2! + 3! + 4!...+10!) % 100 = 13 else // (N >= 10) return 13;}// Driver code let N = 1; for (N = 1; N <= 10; N++) document.write("For N = " + N + " : " + get_last_two_digit(N) + "<br>");// This code is contributed by Mayank Tyagi</script> |
For N = 1 : 1 For N = 2 : 3 For N = 3 : 9 For N = 4 : 33 For N = 5 : 53 For N = 6 : 73 For N = 7 : 13 For N = 8 : 33 For N = 9 : 13 For N = 10 : 13
Time Complexity: O(1), the loop can run for a maximum of 100 times in the worst case.
Auxiliary Space: O(1) as no extra space is used.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
