Dado un número n, encuentre el último dígito distinto de cero en n!.
Ejemplos:
Input : n = 5 Output : 2 5! = 5 * 4 * 3 * 2 * 1 = 120 Last non-zero digit in 120 is 2. Input : n = 33 Output : 8
Una solución simple es primero encontrar n!, luego encontrar el último dígito distinto de cero de n. Esta solución no funciona ni siquiera para números ligeramente grandes debido al desbordamiento aritmético.
Una mejor solución se basa en la siguiente fórmula recursiva
Let D(n) be the last non-zero digit in n!
If tens digit (or second last digit) of n is odd
D(n) = 4 * D(floor(n/5)) * D(Unit digit of n)
If tens digit (or second last digit) of n is even
D(n) = 6 * D(floor(n/5)) * D(Unit digit of n)
Ilustración de la fórmula:
Para los números menores de 10, podemos encontrar fácilmente el último dígito distinto de cero mediante la solución simple anterior, es decir, primero calculando n! y luego encontrando el último dígito.
D(1) = 1, D(2) = 2, D(3) = 6, D(4) = 4, D(5) = 2,
D(6) = 2, D(7) = 4, D (8) = 2, D(9) = 8.
D(1) to D(9) are assumed to be precomputed.
Example 1: n = 27 [Second last digit is even]:
D(27) = 6 * D(floor(27/5)) * D(7)
= 6 * D(5) * D(7)
= 6 * 2 * 4
= 48
Last non-zero digit is 8
Example 2: n = 33 [Second last digit is odd]:
D(33) = 4 * D(floor(33/5)) * D(3)
= 4 * D(6) * 6
= 4 * 2 * 6
= 48
Last non-zero digit is 8
¿Cómo funciona la fórmula anterior?
La siguiente explicación proporciona intuición detrás de la fórmula. Los lectores pueden consultar Consulte http://math.stackexchange.com/questions/130352/last-non-zero-digit-of-a-factorial para una prueba completa.
14! = 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 *
6 * 5 * 4 * 3 * 2 * 1
Since we are asked about last non-zero digit,
we remove all 5's and equal number of 2's from
factors of 14!. We get following:
14! = 14 * 13 * 12 * 11 * 2 * 9 * 8 * 7 *
6 * 3 * 2 * 1
Now we can get last non-zero digit by multiplying
last digits of above factors!
¡Posada! un número de 2 es siempre más que un número de 5. Para eliminar los 0 finales, eliminamos los 5 y el mismo número de 2.
Sea a = piso (n/5), b = n % 5. Después de eliminar un número igual de 5 y 2, ¡podemos reducir el problema de n! a 2a * a ! * ¡b!
D(n) = 2 a * D(a) * D(b)
Implementación:
C++
// C++ program to find last non-zero digit in n!
#include<bits/stdc++.h>
using namespace std;
// Initialize values of last non-zero digit of
// numbers from 0 to 9
int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
int lastNon0Digit(int n)
{
if (n < 10)
return dig[n];
// Check whether tens (or second last) digit
// is odd or even
// If n = 375, So n/10 = 37 and (n/10)%10 = 7
// Applying formula for even and odd cases.
if (((n/10)%10)%2 == 0)
return (6*lastNon0Digit(n/5)*dig[n%10]) % 10;
else
return (4*lastNon0Digit(n/5)*dig[n%10]) % 10;
}
// Driver code
int main()
{
int n = 14;
cout << lastNon0Digit(n);
return 0;
}
C
// C program to find last non-zero digit in n!
#include<stdio.h>
// Initialize values of last non-zero digit of
// numbers from 0 to 9
int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
int lastNon0Digit(int n)
{
if (n < 10)
return dig[n];
// Check whether tens (or second last) digit
// is odd or even
// If n = 375, So n/10 = 37 and (n/10)%10 = 7
// Applying formula for even and odd cases.
if (((n/10) % 10) % 2 == 0)
return (6*lastNon0Digit(n/5)*dig[n%10]) % 10;
else
return (4*lastNon0Digit(n/5)*dig[n%10]) % 10;
}
// Driver code
int main()
{
int n = 14;
printf("%d",lastNon0Digit(n));
return 0;
}
// This code is contributed by allwink45.
Java
// Java program to find last
// non-zero digit in n!
class GFG
{
// Initialize values of last non-zero digit of
// numbers from 0 to 9
static int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
static int lastNon0Digit(int n)
{
if (n < 10)
return dig[n];
// Check whether tens (or second last)
// digit is odd or even
// If n = 375, So n/10 = 37 and
// (n/10)%10 = 7 Applying formula for
// even and odd cases.
if (((n / 10) % 10) % 2 == 0)
return (6 * lastNon0Digit(n / 5)
* dig[n % 10]) % 10;
else
return (4 * lastNon0Digit(n / 5)
* dig[n % 10]) % 10;
}
// Driver code
public static void main (String[] args)
{
int n = 14;
System.out.print(lastNon0Digit(n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python program to find # last non-zero digit in n! # Initialize values of # last non-zero digit of # numbers from 0 to 9 dig= [1, 1, 2, 6, 4, 2, 2, 4, 2, 8] def lastNon0Digit(n): if (n < 10): return dig[n] # Check whether tens (or second last) digit # is odd or even # If n = 375, So n/10 = 37 and (n/10)%10 = 7 # Applying formula for even and odd cases. if (((n//10)%10)%2 == 0): return (6*lastNon0Digit(n//5)*dig[n%10]) % 10 else: return (4*lastNon0Digit(n//5)*dig[n%10]) % 10 return 0 # driver code n = 14 print(lastNon0Digit(n)) # This code is contributed # by Anant Agarwal.
C#
// C# program to find last
// non-zero digit in n!
using System;
class GFG {
// Initialize values of last non-zero
// digit of numbers from 0 to 9
static int []dig = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
static int lastNon0Digit(int n)
{
if (n < 10)
return dig[n];
// Check whether tens (or second
// last) digit is odd or even
// If n = 375, So n/10 = 37 and
// (n/10)%10 = 7 Applying formula
// for even and odd cases.
if (((n / 10) % 10) % 2 == 0)
return (6 * lastNon0Digit(n / 5) *
dig[n % 10]) % 10;
else
return (4 * lastNon0Digit(n / 5) *
dig[n % 10]) % 10;
}
// Driver code
public static void Main ()
{
int n = 14;
Console.Write(lastNon0Digit(n));
}
}
// This code is contributed by Nitin Mittal.
PHP
<?php
// PHP program to find last
// non-zero digit in n!
// Initialize values of
// last non-zero digit of
// numbers from 0 to 9
$dig = array(1, 1, 2, 6, 4,
2, 2, 4, 2, 8);
function lastNon0Digit($n)
{
global $dig;
if ($n < 10)
return $dig[$n];
// Check whether tens(or second
// last) digit is odd or even
// If n = 375, So n/10 = 37 and
// (n/10)%10 = 7
// Applying formula for even
// and odd cases.
if ((($n / 10) % 10) % 2 == 0)
return (6 * lastNon0Digit($n / 5) *
$dig[$n % 10]) % 10;
else
return (4 * lastNon0Digit($n / 5) *
$dig[$n % 10]) % 10;
}
// Driver code
$n = 14;
echo(lastNon0Digit($n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to find
// last non-zero digit in n!
// Initialize values of last non-zero
// digit of numbers from 0 to 9
let dig = [1, 1, 2, 6, 4, 2, 2, 4, 2, 8];
function lastNon0Digit(n)
{
if (n < 10)
return dig[n];
// Check whether tens (or second
// last) digit is odd or even
// If n = 375, So n/10 = 37 and
// (n/10)%10 = 7 Applying formula
// for even and odd cases.
if ((parseInt(n / 10, 10) % 10) % 2 == 0)
return (6 * lastNon0Digit(parseInt(n / 5, 10))
* dig[n % 10]) % 10;
else
return (4 * lastNon0Digit(parseInt(n / 5, 10))
* dig[n % 10]) % 10;
}
let n = 14;
document.write(lastNon0Digit(n));
</script>
Producción
2
Una solución simple basada en la recursión que tiene la complejidad temporal O (nLog (n)) en el peor de los casos.
Acercarse:-
- Se da que hay que encontrar el último dígito positivo. Ahora un dígito se hace múltiplo de 10 si hay 2 y 5. Producen un número con el último dígito 0.
- Ahora lo que podemos hacer es dividir cada elemento de la array en su forma divisible más corta por 5 y aumentar el recuento de tales ocurrencias.
- Ahora divida cada elemento de la array en su forma divisible más corta por 2 y disminuya el recuento de tales ocurrencias. De esta manera, no estamos considerando la multiplicación de 2 y un 5 en nuestra multiplicación (el número de 2 presentes en el resultado de la multiplicación hasta n siempre es mayor que el número 0f 5).
- Multiplique cada número (después de eliminar los pares de 2 y 5) ahora y almacene solo el último dígito tomando el resto por 10.
- Ahora llame recursivamente para números más pequeños por (currentNumber – 1) como parámetro.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Helper Function to return the rightmost non-zero digit
void callMeFactorialLastDigit(int n, int result[], int sumOf5)
{
int number = n; // assaigning to new variable.
if (number == 1)
return; // base case
// To store the count of times 5 can
// divide the number.
while (number % 5 == 0) {
number /= 5;
// increase count of 5
sumOf5++;
}
// Divide the number by
// 2 as much as possible
while (sumOf5 != 0 && (number & 1) == 0) {
number >>= 1; // dividing the number by 2
sumOf5--;
}
/*multiplied result and current number(after
removing pairs) and do modular division to get the
last digit of the resultant number.*/
result[0] = (result[0] * (number % 10)) % 10;
// calling again for (currentNumber - 1)
callMeFactorialLastDigit(n - 1, result, sumOf5);
}
int lastNon0Digit(int n)
{
int result[] = { 1 }; // single element array.
callMeFactorialLastDigit(n, result, 0);
return result[0];
}
int main()
{
cout << lastNon0Digit(7) << endl;
cout << lastNon0Digit(12) << endl;
return 0;
}
// This code is contributed by rameshtravel07.
C
#include <stdio.h>
// Helper Function to return the rightmost non-zero digit
void callMeFactorialLastDigit(int n, int result[], int sumOf5)
{
int number = n; // assaigning to new variable.
if (number == 1)
return; // base case
// To store the count of times 5 can
// divide the number.
while (number % 5 == 0) {
number /= 5;
// increase count of 5
sumOf5++;
}
// Divide the number by
// 2 as much as possible
while (sumOf5 != 0 && (number & 1) == 0) {
number >>= 1;
sumOf5--;
}
/*multiplied result and current number(after
removing pairs) and do modular division to get the
last digit of the resultant number.*/
result[0] = (result[0] * (number % 10)) % 10;
// calling again for (currentNumber - 1)
callMeFactorialLastDigit(n - 1, result, sumOf5);
}
int lastNon0Digit(int n)
{
int result[] = { 1 }; // single element array
callMeFactorialLastDigit(n, result, 0);
return result[0];
}
int main()
{
printf("%d\n",lastNon0Digit(7));
printf("%d",lastNon0Digit(12));
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG {
// Helper Function to return the rightmost non-zero
// digit
public static void
callMeFactorialLastDigit(int n, int[] result,
int sumOf5)
{
int number = n; // assaigning to new variable.
if (number == 1)
return; // base case
// To store the count of times 5 can
// divide the number.
while (number % 5 == 0) {
number /= 5;
// increase count of 5
sumOf5++;
}
// Divide the number by
// 2 as much as possible
while (sumOf5 != 0 && (number & 1) == 0) {
number >>= 1; // dividing the number by 2
sumOf5--;
}
/*multiplied result and current number(after
removing pairs) and do modular division to get the
last digit of the resultant number.*/
result[0] = (result[0] * (number % 10)) % 10;
// calling again for (currentNumber - 1)
callMeFactorialLastDigit(n - 1, result, sumOf5);
}
public static int lastNon0Digit(int n)
{
int[] result = { 1 }; // single element array.
callMeFactorialLastDigit(n, result, 0);
return result[0];
}
public static void main(String[] args)
{
System.out.println(lastNon0Digit(7)); // 3040
System.out.println(lastNon0Digit(12)); // 479001600
}
}
//This code is contributed by KaaL-EL.
Python3
# Helper Function to return the rightmost non-zero digit def callMeFactorialLastDigit(n, result, sumOf5): number = n # assaigning to new variable. if number == 1: return # base case # To store the count of times 5 can # divide the number. while (number % 5 == 0): number = int(number / 5) # increase count of 5 sumOf5 += 1 # Divide the number by # 2 as much as possible while (sumOf5 != 0 and (number & 1) == 0): number >>= 1 # dividing the number by 2 sumOf5 -= 1 """multiplied result and current number(after removing pairs) and do modular division to get the last digit of the resultant number.""" result[0] = (result[0] * (number % 10)) % 10 # calling again for (currentNumber - 1) callMeFactorialLastDigit(n - 1, result, sumOf5) def lastNon0Digit(n): result = [ 1 ] # single element array. callMeFactorialLastDigit(n, result, 0) return result[0] print(lastNon0Digit(7)) # 3040 print(lastNon0Digit(12)) # 479001600 # This code is contributed by suresh07.
C#
using System;
class GFG {
// Helper Function to return the rightmost non-zero
// digit
static void
callMeFactorialLastDigit(int n, int[] result,
int sumOf5)
{
int number = n; // assaigning to new variable.
if (number == 1)
return; // base case
// To store the count of times 5 can
// divide the number.
while (number % 5 == 0) {
number /= 5;
// increase count of 5
sumOf5++;
}
// Divide the number by
// 2 as much as possible
while (sumOf5 != 0 && (number & 1) == 0) {
number >>= 1; // dividing the number by 2
sumOf5--;
}
/*multiplied result and current number(after
removing pairs) and do modular division to get the
last digit of the resultant number.*/
result[0] = (result[0] * (number % 10)) % 10;
// calling again for (currentNumber - 1)
callMeFactorialLastDigit(n - 1, result, sumOf5);
}
static int lastNon0Digit(int n)
{
int[] result = { 1 }; // single element array.
callMeFactorialLastDigit(n, result, 0);
return result[0];
}
static void Main() {
Console.WriteLine(lastNon0Digit(7)); // 3040
Console.WriteLine(lastNon0Digit(12)); // 479001600
}
}
// This code is contributed by mukesh07.
Javascript
<script>
// Helper Function to return the rightmost non-zero
// digit
function callMeFactorialLastDigit(n, result, sumOf5)
{
let number = n; // assaigning to new variable.
if (number == 1)
return; // base case
// To store the count of times 5 can
// divide the number.
while (number % 5 == 0) {
number /= 5;
// increase count of 5
sumOf5++;
}
// Divide the number by
// 2 as much as possible
while (sumOf5 != 0 && (number & 1) == 0) {
number >>= 1; // dividing the number by 2
sumOf5--;
}
/*multiplied result and current number(after
removing pairs) and do modular division to get the
last digit of the resultant number.*/
result[0] = (result[0] * (number % 10)) % 10;
// calling again for (currentNumber - 1)
callMeFactorialLastDigit(n - 1, result, sumOf5);
}
function lastNon0Digit(n)
{
let result = [ 1 ]; // single element array.
callMeFactorialLastDigit(n, result, 0);
return result[0];
}
document.write(lastNon0Digit(7) + "</br>"); // 3040
document.write(lastNon0Digit(12)); // 479001600
// This code is contributed by divyeshrabadiya07
</script>
Producción
4 6
usamos una array de un solo elemento (int[] result = {1}) en lugar de un número entero, ya que Java es Strictly Pass by Value. No permite pasar por referencia para tipos de datos primitivos. Es por eso que usé una array de un solo elemento para que la función recursiva pueda cambiar el valor de la variable (resultado aquí). Si hubiéramos tomado (int resultado = 1), esta variable no se vería afectada.
Este artículo es una contribución de Niteesh kumar y KaaL-EL . 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