Nos dan dos números A y B tales que B >= A. Necesitamos calcular el último dígito de este F resultante tal que F = B!/A! donde 1 = A, B <= 10^18 (A y B son muy grandes).
Ejemplos:
Input : A = 2, B = 4 Output : 2 Explanation : A! = 2 and B! = 24. F = 24/2 = 12 --> last digit = 2 Input : 107 109 Output : 2
Como sabemos, la función factorial crece exponencialmente. Incluso el tipo de datos más grande
no puede contener el factorial de números como 100. Para calcular el factorial de números moderadamente grandes, consulte este .
Aquí las restricciones dadas son muy grandes. Por lo tanto, calcular los dos factoriales y luego
dividirlos y calcular el último dígito es una tarea prácticamente imposible.
Por lo tanto, tenemos que encontrar un enfoque alternativo para desglosar nuestro problema. Se sabe que el último dígito del factorial siempre pertenece al conjunto {0, 1, 2, 4, 6}
El planteamiento es el siguiente: –
1) Evaluamos la diferencia entre B y A
2) Si el (B – A ) >= 5, entonces la respuesta siempre es 0
3) Si la diferencia (B – A) < 5, iteramos de (A+1) a B, los multiplicamos y los almacenamos. multiplication_answer % 10 será nuestra respuesta.
C++
// CPP program to find last digit of a number
// obtained by dividing factorial of a number
// with factorial of another number.
#include <iostream>
using namespace std;
// Function which computes the last digit
// of resultant of B!/A!
int computeLastDigit(long long int A, long long int B)
{
int variable = 1;
if (A == B) // If A = B, B! = A! and B!/A! = 1
return 1;
// If difference (B - A) >= 5, answer = 0
else if ((B - A) >= 5)
return 0;
else {
// If non of the conditions are true, we
// iterate from A+1 to B and multiply them.
// We are only concerned for the last digit,
// thus we take modulus of 10
for (long long int i = A + 1; i <= B; i++)
variable = (variable * (i % 10));
return variable % 10;
}
}
// driver function
int main()
{
cout << computeLastDigit(2632, 2634);
return 0;
}
C
// CPP program to find last digit of a number
// obtained by dividing factorial of a number
// with factorial of another number.
#include <stdio.h>
// Function which computes the last digit
// of resultant of B!/A!
int computeLastDigit(long long int A, long long int B)
{
int variable = 1;
if (A == B)
return 1;
// If difference (B - A) >= 5, answer = 0
else if ((B - A) >= 5)
return 0;
else {
// If non of the conditions are true, we
// iterate from A+1 to B and multiply them.
// We are only concerned for the last digit,
// thus we take modulus of 10
for (long long int i = A + 1; i <= B; i++)
variable = (variable * (i % 10));
return variable % 10;
}
}
// driver function
int main()
{
long long int a=2632;
long long int b=2634;
int ans=computeLastDigit(a,b);
printf("%d",ans);
return 0;
}
// This code is contributed by allwink45.
Java
// Java program to find last digit of a number
// obtained by dividing factorial of a number
// with factorial of another number.
import java.io.*;
class GFG {
// Function which computes the last digit
// of resultant of B!/A!
static int computeLastDigit(long A, long B)
{
int variable = 1;
if (A == B) // If A = B, B! = A! and B!/A! = 1
return 1;
// If difference (B - A) >= 5, answer = 0
else if ((B - A) >= 5)
return 0;
else {
// If non of the conditions are true, we
// iterate from A+1 to B and multiply them.
// We are only concerned for the last digit,
// thus we take modulus of 10
for (long i = A + 1; i <= B; i++)
variable = (int)(variable * (i % 10)) % 10;
return variable % 10;
}
}
// driver function
public static void main(String[] args)
{
System.out.println(computeLastDigit(2632, 2634));
}
}
// This article is contributed by Prerna Saini
Python3
# Python program to find # last digit of a number # obtained by dividing # factorial of a number # with factorial of another number. # Function which computes # the last digit # of resultant of B!/A! def computeLastDigit(A,B): variable = 1 if (A == B): # If A = B, B! = A! and B!/A! = 1 return 1 # If difference (B - A) >= 5, answer = 0 elif ((B - A) >= 5): return 0 else: # If non of the conditions # are true, we # iterate from A+1 to B # and multiply them. # We are only concerned # for the last digit, # thus we take modulus of 10 for i in range(A + 1, B + 1): variable = (variable * (i % 10)) % 10 return variable % 10 # driver function print(computeLastDigit(2632, 2634)) # This code is contributed # by Anant Agarwal.
C#
// C# program to find last digit of
// a number obtained by dividing
// factorial of a number with
// factorial of another number.
using System;
class GFG {
// Function which computes the last
// digit of resultant of B!/A!
static int computeLastDigit(long A, long B)
{
int variable = 1;
// If A = B, B! = A!
// and B!/A! = 1
if (A == B)
return 1;
// If difference (B - A) >= 5,
// answer = 0
else if ((B - A) >= 5)
return 0;
else {
// If non of the conditions are true, we
// iterate from A+1 to B and multiply them.
// We are only concerned for the last digit,
// thus we take modulus of 10
for (long i = A + 1; i <= B; i++)
variable = (int)(variable *
(i % 10)) % 10;
return variable % 10;
}
}
// Driver Code
public static void Main()
{
Console.WriteLine(computeLastDigit(2632, 2634));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find last digit of a number
// obtained by dividing factorial of a number
// with factorial of another number.
// Function which computes the last
// digit of resultant of B!/A!
function computeLastDigit($A, $B)
{
$variable = 1;
// If A = B, B! = A!
// and B!/A! = 1
if ($A == $B)
return 1;
// If difference (B - A) >= 5,
// answer = 0
else if (($B - $A) >= 5)
return 0;
else
{
// If non of the conditions
// are true, we iterate from
// A+1 to B and multiply them.
// We are only concerned for
// the last digit, thus we
// take modulus of 10
for ($i = $A + 1; $i <= $B; $i++)
$variable = ($variable * ($i % 10)) % 10;
return $variable % 10;
}
}
// Driver Code
echo computeLastDigit(2632, 2634);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find last digit of a number
// obtained by dividing factorial of a number
// with factorial of another number.
// Function which computes the last digit
// of resultant of B!/A!
function computeLastDigit(A, B)
{
let variable = 1;
if (A == B) // If A = B, B! = A! and B!/A! = 1
return 1;
// If difference (B - A) >= 5, answer = 0
else if ((B - A) >= 5)
return 0;
else {
// If none of the conditions are true, we
// iterate from A+1 to B and multiply them.
// We are only concerned for the last digit,
// thus we take modulus of 10
for (let i = A + 1; i <= B; i++)
variable = (variable * (i % 10)) % 10;
return variable % 10;
}
}
// driver function
document.write(computeLastDigit(2632, 2634));
// This code is contributed by Surbhi Tyagi
</script>
Producción:
2
Complejidad Temporal: O(1).
Espacio Auxiliar: O( 1 ), ya que no se ha ocupado ningún espacio extra.
Este artículo es una contribución de Shivani Mittal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA