Input: N = 7
Output: 40
Explanation: 7! = 5040
Input: N = 11
Output: 00
We can observe that for N >= 10, the last two places of its factorial will contain 0’s only. Hence N! % 100 for any N >= 10 will always be 0. So we just calculate the factorial if N < 10 and extract the final two digits.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
void lastTwoDigits( long long N)
{
if (N >= 10) {
cout << "00" ;
return ;
}
long long fac = 1;
for ( int i = 1; i <= N; i++)
fac = (fac * i) % 100;
cout << fac;
}
int main()
{
int N = 7;
lastTwoDigits(N);
}
|
Java
import java.util.*;
class GFG{
static void lastTwoDigits( double N)
{
if (N >= 10 )
{
System.out.print( "00" );
return ;
}
double fac = 1 ;
for ( int i = 1 ; i <= N; i++)
fac = (fac * i) % 100 ;
System.out.print(fac);
}
public static void main(String args[])
{
int N = 7 ;
lastTwoDigits(N);
}
}
|
Python3
def lastTwoDigits(N):
if (N > = 10 ):
print ( "00" , end = "")
return
fac = 1
for i in range ( 1 , N + 1 ):
fac = (fac * i) % 100
print (fac)
if __name__ = = '__main__' :
N = 7
lastTwoDigits(N)
|
C#
using System;
class GFG{
static void lastTwoDigits( double N)
{
if (N >= 10)
{
Console.Write( "00" );
return ;
}
double fac = 1;
for ( int i = 1; i <= N; i++)
fac = (fac * i) % 100;
Console.Write(fac);
}
public static void Main()
{
int N = 7;
lastTwoDigits(N);
}
}
|
Javascript
<script>
function lastTwoDigits(N)
{
if (N >= 10) {
cout << "00" ;
return ;
}
let fac = 1;
for (let i = 1; i <= N; i++)
fac = (fac * i) % 100;
document.write(fac);
}
let N = 7;
lastTwoDigits(N);
</script>
|
Time complexity: O(n) since using a for loop
Auxiliary space: O(1) because it is using constant space
This approach uses the math library in Python to calculate the factorial of the input number n. The factorial result is converted to a string and the last two digits are extracted using slicing. Finally, the last two digits are returned in reverse order to get the correct result.
Algorithm
1. Calculate the factorial of the input number n using the math.factorial() function.
2. Convert the result to a string and reverse it.
3. Extract the last two characters using slicing.
4. Reverse the extracted last two characters and return them as a string.
C++
#include <iostream>
#include <cmath>
std::string lastTwoDigitsFactorial( int n) {
long long factorial = 1;
for ( int i = 1; i <= n; i++) {
factorial *= i;
}
std::string factorialStr = std::to_string(factorial);
std::string reversedStr = "" ;
for ( int i = factorialStr.length() - 1; i >= 0; i--) {
reversedStr += factorialStr[i];
}
std::string lastTwoDigits = reversedStr.substr(0, 2);
std::string result = "" ;
for ( int i = 1; i >= 0; i--) {
result += lastTwoDigits[i];
}
return result;
}
int main() {
int n1 = 7;
int n2 = 11;
std::string result1 = lastTwoDigitsFactorial(n1);
std::string result2 = lastTwoDigitsFactorial(n2);
std::cout << "Last two digits of " << n1 << "! : " << result1 << std::endl;
std::cout << "Last two digits of " << n2 << "! : " << result2 << std::endl;
return 0;
}
|
Java
import java.util.*;
public class GFG {
static String lastTwoDigitsFactorial( int n)
{
long factorial = 1 ;
for ( int i = 1 ; i <= n; i++) {
factorial *= i;
}
String factorialStr = Long.toString(factorial);
StringBuilder reversedStr = new StringBuilder();
for ( int i = factorialStr.length() - 1 ; i >= 0 ;
i--) {
reversedStr.append(factorialStr.charAt(i));
}
String lastTwoDigits = reversedStr.substring( 0 , 2 );
StringBuilder result = new StringBuilder();
for ( int i = 1 ; i >= 0 ; i--) {
result.append(lastTwoDigits.charAt(i));
}
return result.toString();
}
public static void main(String[] args)
{
int n1 = 7 ;
int n2 = 11 ;
String result1 = lastTwoDigitsFactorial(n1);
String result2 = lastTwoDigitsFactorial(n2);
System.out.println( "Last two digits of " + n1
+ "! : " + result1);
System.out.println( "Last two digits of " + n2
+ "! : " + result2);
}
}
|
Python3
import math
def last_two_digits_factorial(n):
factorial = str (math.factorial(n))
z = factorial[:: - 1 ]
last_two_digits = z[: 2 ]
return last_two_digits[:: - 1 ]
print (last_two_digits_factorial( 7 ))
print (last_two_digits_factorial( 11 ))
|
C#
using System;
class Program
{
static string LastTwoDigitsFactorial( int n)
{
long factorial = 1;
for ( int i = 1; i <= n; i++)
{
factorial *= i;
}
string factorialStr = factorial.ToString();
char [] reversedArray = factorialStr.ToCharArray();
Array.Reverse(reversedArray);
string reversedStr = new string (reversedArray);
string lastTwoDigits = reversedStr.Substring(0, 2);
char [] resultArray = lastTwoDigits.ToCharArray();
Array.Reverse(resultArray);
string result = new string (resultArray);
return result;
}
static void Main()
{
int n1 = 7;
int n2 = 11;
string result1 = LastTwoDigitsFactorial(n1);
string result2 = LastTwoDigitsFactorial(n2);
Console.WriteLine( "Last two digits of " + n1 + "! : " + result1);
Console.WriteLine( "Last two digits of " + n2 + "! : " + result2);
}
}
|
Javascript
function GFG(n) {
let factorial = BigInt(1);
for (let i = 1; i <= n; i++) {
factorial *= BigInt(i);
}
let factorialStr = factorial.toString();
let reversedStr = factorialStr.split( '' ).reverse().join( '' );
let lastTwoDigits = reversedStr.slice(0, 2);
return lastTwoDigits.split( '' ).reverse().join( '' );
}
console.log(GFG(7));
console.log(GFG(11));
|
Output
Last two digits of 7! : 40
Last two digits of 11! : 00
Time complexity: The time complexity of this program is O(n) as it calculates the factorial using the math.factorial() function which takes O(n) time.
Space complexity: The space complexity of this program is O(n) as it creates a string of length n to store the factorial result.
This approach uses in this code is to create a lambda function that takes a positive integer as input, and uses the reduce() function from the functools module to calculate the factorial of the input number modulo 100. The reduce() function takes an anonymous function as its first argument that multiplies the accumulator (x) by the next element in the range (y), and returns the result modulo 100. The range starts from 1 and goes up to n+1, where n is the input integer. The initial value of the accumulator is set to 1, since any number multiplied by 1 equals that number.
Algorithm
1. Import the reduce() function from the functools module
2. Initialize a positive integer N
3. Create a lambda function called “last_two_digits” that takes an integer argument n
4. In the lambda function, use the reduce() function to calculate the factorial of n modulo 100
5. The reduce() function takes an anonymous function that multiplies the accumulator by the next element in the range, and returns the result modulo 100
6. The range starts from 1 and goes up to n+1
7. The initial value of the accumulator is set to 1
8. Call the lambda function with N as an argument
9. Print the result as a string formatted to two digits using the “{:02d}” format specifier
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int N = 11;
auto last_two_digits = []( int n) {
int result = 1;
for ( int i = 1; i <= n; i++) {
result
= (result * i)
% 100;
}
return result;
};
int result = last_two_digits(N);
cout << setfill( '0' ) << setw(2) << result << endl;
return 0;
}
|
Java
import java.util.function.Function;
public class GFG {
public static void main(String[] args)
{
int N = 11 ;
Function<Integer, Integer> lastTwoDigits = n ->
{
int result = 1 ;
for ( int i = 1 ; i <= n; i++) {
result = (result * i)
% 100 ;
}
return result;
};
int result = lastTwoDigits.apply(N);
System.out.printf( "%02d%n" , result);
}
}
|
Python3
from functools import reduce
N = 11
last_two_digits = lambda n: reduce ( lambda x, y: (x * y) % 100 , range ( 1 , n + 1 ), 1 )
print ( "{:02d}" . format (last_two_digits(N)))
|
C#
using System;
class Program
{
static void Main()
{
int N = 11;
Func< int , int > lastTwoDigits = n =>
{
int resultFactorial = 1;
for ( int i = 1; i <= n; i++)
{
resultFactorial = (resultFactorial * i) % 100;
}
return resultFactorial;
};
int result = lastTwoDigits(N);
Console.WriteLine(result.ToString( "D2" ));
}
}
|
Javascript
let lastTwoDigits = (n) => {
let result = 1;
for (let i = 1; i <= n; i++) {
result = (result * i) % 100;
}
return result;
};
let N = 11;
let result = lastTwoDigits(N);
let resultString = result.toString().padStart(2, '0' );
console.log(resultString);
|
Time Complexity: O(N), where N is the input integer. This is because the reduce() function iterates over the range from 1 to N+1, which takes O(N) time.
Auxiliary Space: O(1), since only a constant amount of memory is used to store the input integer, the lambda function, and the result. The reduce() function only stores the accumulator and the next element in the range at any given time, so the memory usage does not depend on the size of the input integer.
- Start with the input value n passed to the function.
- Create an empty list called dp to store the computed factorials.
- Append the value 1 to the dp list as the factorial of 0 is 1.
- Enter a loop that iterates from 1 to n (inclusive) using the variable i.
- Inside the loop, compute the factorial of i by multiplying the previous factorial in the dp list (dp[-1]) with i. Take the modulus of the result with 100 to keep only the last two digits.
- Append the computed factorial to the dp list.
- After the loop, retrieve the last element from the dp list using dp[-1], which represents the factorial of n.
- Convert the factorial to a string using str().
- If the factorial has fewer than two digits, pad it with leading zeroes using the zfill() method with an argument of 2.
- Return the resulting string as the last two digits of the factorial.
C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;
string last_two_digits_factorial( int n) {
vector< int > dp(1, 1);
for ( int i = 1; i <= n; ++i) {
dp.push_back((dp.back() * i) % 100);
}
return to_string(dp.back());
}
int main() {
int n = 7;
string result = last_two_digits_factorial(n);
while (result.length() < 2) {
result = "0" + result;
}
cout << result << endl;
return 0;
}
|
Java
import java.util.ArrayList;
import java.util.List;
public class Main {
public static String lastTwoDigitsFactorial( int n) {
List<Integer> dp = new ArrayList<>();
dp.add( 1 );
for ( int i = 1 ; i <= n; ++i) {
dp.add((dp.get(dp.size() - 1 ) * i) % 100 );
}
String result = dp.get(dp.size() - 1 ).toString();
while (result.length() < 2 ) {
result = "0" + result;
}
return result;
}
public static void main(String[] args) {
int n = 7 ;
String result = lastTwoDigitsFactorial(n);
System.out.println(result);
}
}
|
Python3
def last_two_digits_factorial(n):
dp = [ 1 ]
for i in range ( 1 , n + 1 ):
dp.append((dp[ - 1 ] * i) % 100 )
return str (dp[ - 1 ]).zfill( 2 )
n = 7
result = last_two_digits_factorial(n)
print (result)
|
C#
using System;
class MainClass {
static string LastTwoDigitsFactorial( int n) {
var dp = new System.Collections.Generic.List< int > { 1 };
for ( int i = 1; i <= n; ++i) {
dp.Add((dp[dp.Count - 1] * i) % 100);
}
return dp[dp.Count - 1].ToString();
}
public static void Main( string [] args) {
int n = 7;
string result = LastTwoDigitsFactorial(n);
while (result.Length < 2) {
result = "0" + result;
}
Console.WriteLine(result);
}
}
|
Javascript
function lastTwoDigitsFactorial(n) {
const dp = [1];
for (let i = 1; i <= n; ++i) {
dp.push((dp[dp.length - 1] * i) % 100);
}
let result = dp[dp.length - 1].toString();
while (result.length < 2) {
result = "0" + result;
}
return result;
}
const n = 7;
const result = lastTwoDigitsFactorial(n);
console.log(result);
|
The initialization of the dp list with a single element takes constant time, O(1).
The loop iterates n times, performing constant time operations in each iteration. Therefore, the loop has a time complexity of O(n).
Within the loop, the list dp is appended with a new element, which takes constant time, O(1).
The computation of (dp[-1] * i) % 100 also takes constant time, O(1).
Finally, retrieving the last element from the dp list and converting it to a string using str() takes constant time, O(1).
Hence, the overall time complexity of the last_two_digits_factorial() function is O(1) + O(n) + O(1) + O(1) + O(1) = O(n).
The dp list is initialized with a single element, taking constant space, O(1).
The dp list grows to store n+1 elements, so it occupies space proportional to n. Hence, the space complexity for the dp list is O(n).
The additional space used to store the result variable and the function parameters is constant, O(1).
Therefore, the overall space complexity of the last_two_digits_factorial() function is O(n) + O(1) = O(n).