Dado un número N, la tarea es encontrar la unidad y el dígito de las decenas de los primeros N factoriales de números naturales, es decir, los dos últimos dígitos de 1!+2!+3!+….N! donde N<=10e18.
Ejemplos:
Input : n = 2 Output :3 1! + 2! = 3 Last two digit is 3 Input :4 Output :33 1!+2!+3!+4!=33 Last two digit is 33
Enfoque ingenuo: en este enfoque, simplemente calcule el factorial de cada número y encuentre la suma de estos. Finalmente obtenga el dígito de la unidad y el lugar de las decenas de la suma. Esto llevará mucho tiempo y cálculos innecesarios.
Enfoque eficiente: en este enfoque, solo se calcularán las unidades y las decenas de N en el rango [1, 10], porque:
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8!=40320
9!=362880
10!=3628800
y así sucesivamente.
Como 10 != 3628800, y factorial de número mayor que 10 tienen dos ceros finales. Entonces, N>=10 no contribuye en el lugar de las unidades y las decenas mientras se hace la suma.
Por lo tanto,
si (n < 10)
respuesta = (1 ! + 2 ! +..+ n !) % 100;
otra
respuesta = (1 ! + 2 ! + 3 ! + 4 !+ 5 ! + 6 ! + 7 ! + 8 ! + 9 ! + 10 !) % 100;
Nota: Sabemos (1! + 2! + 3! + 4!+…+10!) % 100 = 13
Así que siempre devolvemos 3 cuando n es mayor
que 4.
A continuación se muestra la implementación del enfoque anterior.
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 digit
int 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 code
int 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 factorials
public 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 digit
def 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 Code
N = 1
for 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 factorials
using System;
class GFG
{
// 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()
{
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 digit
function 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 digit
function 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
Publicación traducida automáticamente
Artículo escrito por sahilshelangia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA