Último dígito distinto de cero de n!

22

Dado un entero 1 ≤ N ≤ 1,000,000 como entrada, ¡emite el último dígito distinto de cero de N! , donde ! es el factorial (el producto de todos los números del 1 al N , inclusive). Esta es la secuencia OEIS A008904 .

Su programa necesita terminar dentro de 10 segundos en una máquina razonable para cualquier entrada válida.

Casos de prueba

1 => 1
2 => 2
3 => 6
4 => 4
5 => 2
6 => 2
7 => 4
8 => 2
9 => 8
10 => 8
100 => 4
1000 => 2
10000 => 8
100000 => 6
1000000 => 4

Este es un por lo que gana el código más corto en bytes.

fR0DDY
fuente
¿Función única o programa completo?
Joey
@joey No, son solo casos de prueba. Entrada única, salida única.
fR0DDY
@joey Programa completo.
fR0DDY
1
Se desaconseja el requisito de un programa completo ...
Erik the Outgolfer
2
@EriktheOutgolfer esto es de hace ~ 7 años, así que no creo que eso se haya determinado en ese momento
NoOneIsHere

Respuestas:

8

Ruby - 63 caracteres

f=->n{n<2?1:6*[1,1,2,6,4,4,4,8,4,6][n%10]*3**(n/5%4)*f[n/5]%10}

Fuente: http://oeis.org/A008904

Maneja hasta mil dígitos por segundo.

Prueba

irb(main):014:0> for n in 2..6
irb(main):015:1> puts f[10**n]
irb(main):016:1> end
4
2
8
6
4
Dogbert
fuente
11

Mathematica, 45 36 bytes

Last@Select[IntegerDigits[#!],#>0&]&

Muy legible para una respuesta ganadora. :) (Por otra parte, todavía no hay presentación de GolfScript & Co.).

Esto maneja la entrada 1,000,000 en aproximadamente 5 segundos en mi máquina.

Martin Ender
fuente
1
Mathematica es prácticamente el lenguaje perfecto para esta pregunta.
Michael Stern
4

Python - 75

n=input()
g=1
while n:
 g*=n
 while g%10<1:g/=10
 g%=10**9
 n-=1
print g%10
JPvdMerwe
fuente
3

PARI / GP - 27 bytes

Esto cambia la velocidad por el tamaño: el caso de prueba lleva mucho tiempo (~ 6 segundos).

n->n!/10^valuation(n!,5)%10

Esta versión es mucho más rápida (~ 15 microsegundos) pero toma 81 bytes:

n->r=1;while(n,r*=Mod(4,10)^(n\10%2)*[1,2,6,4,2,2,4,2,8][max(n%10,1)];n\=5);lift(r)

Puede usar este código (no golfizado) para probar:

[%(10^n) | n <- [1..6]]
Charles
fuente
2

Windows PowerShell, 53 56 59 60 63 73 90

($a=1).."$input"|%{$a="$($a*$_)".trim('0')%1e7}
$a%10

Notas:

  • Tarda más de un minuto para un número cercano a 100,000. Sin embargo, eliminar ceros al final requiere una conversión a cadena, hacer cálculos requiere un número, por lo que las conversiones son inevitables en cualquier caso.

Historia:

  • 2011-02-08 10:31 (90) - Primer intento.
  • 2011-02-08 10:33 (73) - El módulo es más corto que cortar y unir.
  • 2011-02-08 10:34 (63) - Recorte innecesario.
  • 2011-02-08 10:37 (60) - Lanzamiento innecesario a un número. Modulus hace eso bien, ya.
  • 2011-02-08 10:40 (59) - Algunas líneas.
  • 2011-02-08 11:00 (56) - ¿Qué dije antes acerca de que el módulo es más corto? Se aplica a la salida también.
  • 2011-02-08 11:01 (53) - Casting $inputa una cadena es suficiente; El reparto intse aplica implícitamente.
Joey
fuente
2

Perl, 53 58 61 caracteres

Todo el espacio en blanco se puede eliminar, pero lo dejé para "legibilidad". Nota: no usar alguna fórmula explícita tonta de Sloane.

sub f {
    $_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $_[0];
    $1 % 10
}

Calcula f (10 ^ 6) en 8.7 segundos en mi máquina.

Actualización : OP quería que fuera un programa completo:

$_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $ARGV[0];
print $1 % 10

Eso lo convierte en 55 caracteres.


fuente
2

CJam - 28

1ri{I)*_AbW%{}#A\#/1e7%}fIA%

Puede probarlo en http://cjam.aditsu.net/ para valores de hasta 10000 aproximadamente; para números más grandes debe usar el intérprete de java . 1000000 se ejecuta en aproximadamente 3 segundos en mi computadora portátil.

Explicación:

Desafortunadamente, la solución directa es demasiado lenta, por lo que solo mantengo los últimos 7 dígitos (antes de los ceros finales) después de cada multiplicación.

1           push 1 on the stack
ri          read a token and convert to integer
{           loop (for I from 0 to N - 1)
    I)      push I and increment
    *       multiply with the previous value (initially 1)
    _Ab     duplicate and convert to array of digits
    W%      reverse array
    {}#     find the position of the first non-zero digit
    A\#     raise 10 to that power
    /       divide, thus removing all trailing zeros
    1e7%    keep the remainder modulo 10000000
}fI         end for loop
A%          get the last digit

Nota: este lenguaje es mucho más nuevo que la pregunta.

aditsu
fuente
2

Mathematica, 34 bytes

Mod[#!/10^IntegerExponent[#!],10]&
alephalpha
fuente
2

05AB1E , 4 bytes

!0м¤

Pruébalo en línea!

Explicación

!0    # Push the factorial of the input and 0
  м   # Remove the occurences of 0 in the factorial
   ¤  # Push the last element, implicit display
Kaldo
fuente
1
Se agotó el tiempo de espera de la versión TIO (60 segundos) en el último caso de prueba: ¿cómo lo consiguió en 10 segundos en una "máquina razonable"?
Toby Speight
2

Jalea , 4 bytes

!Ṛȯ/

Pruébalo en línea!

Explicación

Utiliza el hecho de que cuando (se invierte una lista; no se vectoriza) se aplica a un entero, Dprimero toma automáticamente (dígitos).

Con entrada 8:

!Ṛȯ/
!     Factorial: 8! = 40320
 Ṛ    Reverse: [0,2,3,0,4]
   /  Reduce by...
  ȯ   ...logical OR: ((((0ȯ2)ȯ3)ȯ0)ȯ4) = first truthy element = 2

No creo que haya un "primer elemento de verdad" de un byte (que ȯ/actúa como), pero si lo hay, se puede acortar a tres bytes en total.

dylnan
fuente
2

Java (OpenJDK 8) , 62 bytes

n->{long f=n;for(;n>1||f%10==0;)f=n>1?f*--n:f/10;return f%10;}

Pruébalo en línea!

Similar a @Kevin Cruijssen pero ahorra 5 bytes combinando los bucles.

científico de rocas
fuente
Bienvenido a PPCG! Bonito primer post! ¡Espero que te quedes!
Rɪᴋᴇʀ
Bienvenido a PPCG! Estoy de acuerdo con @Riker, excelente primer post. Bien hecho golfing mi código combinando los bucles. Puede jugar 1 byte más en su respuesta actual reemplazando ||con |, y un byte adicional reemplazando ==0con <1. ¡Disfruta tu estancia!
Kevin Cruijssen
2

C, 150 140 135 bytes

r,d;f(k,x){r=x<5?3:f(k+1,x/5);return(d=x%5)?r*"33436"[d]*(1<<d*k%4)%5:r;}main(int c,char**v){c=atoi(*++v);printf("%d",c<2?1:2*f(0,c));}

Esta es la versión para sistemas ASCII; reemplace la cadena 33436con 11214un sistema EBCDIC, o con\1\1\2\1\4 un programa portátil.

Las soluciones C están un poco obstaculizadas por el requisito de proporcionar un programa completo; sin embargo, esto responde la pregunta completamente.

Pruébelo en línea (requiere Javascript):

Explicación

Se basa en el algoritmo descrito en el dígito menos nulo menos significativo de n! , volteamos para que recurramos para encontrar la potencia más alta de cinco, y hagamos el cálculo al salir. Las tablas de constantes eran demasiado grandes, así que las reduje al encontrar una relación entre el residuo anterior r, el dígito actual dy la profundidad de recursión k:

     0    1       2       3    4  =d
  0  0  3×2^k  1×2^2k  3×2^3k  2
  1  1  1×2^k  2×2^2k  1×2^3k  4
r 2  2  2×2^k  4×2^2k  2×2^3k  3
  3  3  3×2^k  3×2^2k  3×2^3k  2
  4  4  4×2^k  4×2^2k  4×2^3k  1

Para r>0, esto se resuelve a veces constantes rveces 2^dk(mod 5); las constantes están a[]abajo (en el código de golf). También observamos que (2^4)%5es 1, por lo que podemos reducir el exponente para evitar desbordar el rango de int.

const int a[] = { 1, 1, 2, 1, 4 };
int f(int k, int x){
    int r = x<5 ? 3 : f(k+1,x/5); /* residue - from recursing to higher-order quinary digits */
    int d = x%5;
    if (!d)
        return r;
    return r * a[d] * (1<<d*k%4) % 5;
}

int main(int c, char **v)
{
    c = atoi(*++v);
    printf("%d",
           c<2
           ? 1                  /* special-case 0 & 1 */
           : 2*f(0,c));         /* otherwise, it's 2 times r */
}

Pruebas:

$ for i in 100 1000 10000 100000; do echo $i: `./694 $i`; done
100: 4
1000: 2
10000: 8
100000: 6
1000000: 4

El rendimiento también es respetable. Aquí hay una entrada máxima para un sistema con 32 bits int:

$ time ./694 2147483647
8
real    0m0.001s
user    0m0.000s
sys     0m0.000s

También obtuve los mismos tiempos con un máximo de 64 bits int.

Toby Speight
fuente
1
Puede ser interesante observar que 2147483647!tiene más de 19 mil millones de dígitos y (2^63-1)!más de 170,000,000,000,000,000,000 de dígitos, por lo que esta es una gran victoria sobre el cálculo de los factores. 1000000!como se especifica en la pregunta, es factible calcularlo en el hardware actual; eso es solo 5½ millones de dígitos. :-)
Toby Speight
1

PHP - 105

 <?foreach(explode("\n",`cat`)as$n)if($n){$f=rtrim(gmp_strval(gmp_fact($n)),'0');echo substr($f,-1)."\n";}

Se ejecuta en menos de 10 segundos con el caso de prueba dado.

Arnaud Le Blanc
fuente
1

Python3

239 caracteres

Puede hacer 10000 en ~ 3.2 segundos (Ideone me corta a los 8 segundos, estoy seguro de que tomará más de 10 segundos :()

from functools import *
N=100
r=range
s=(p for p in r(2,N)if all(p%n>0for n in r(2,p)))
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=list([p,f(N,p)]for p in s)
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:x[0]**x[1],e))%10)

Python2.6

299 caracteres (un poco más rápido)

from itertools import *
N=100000
r=xrange
def s(c=count(2)):
        while 1:p=c.next();c=ifilter(p.__rmod__,c);yield p
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=[[p,f(N,p)]for p in takewhile(lambda x:x<N,s())]
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:pow(x[0],x[1],10),e))%10)
st0le
fuente
1

Haskell, 78 personajes

f n=head$dropWhile(=='0')$reverse$show$product[1..n]
main=interact(show.f.read)

(¡Probablemente deba compilarse para calcular 1,000,000! En 10 segundos).

stusmith
fuente
Guarde dos caracteres, reemplácelo foldl1con product(cf codegolf.stackexchange.com/questions/607/find-the-factorial/… ). Pero, ¿has probado con 1000000? ?
JB
PD: no es un programa completo.
JB
Lo siento, lo hice antes de que se aclarara en los comentarios. Lo actualizaré.
stusmith
1

J - 42 40 caracteres

Todo un programa. Guarde este programa en un archivo y ejecútelo jconsole script.ijs 1234. Tenga en cuenta que este programa no sale del intérprete después de imprimir un resultado. Escriba ^Do exit]0para salir del intérprete.

echo([:{:@(#~*)10&#.inv@*)/1+i.".>{:ARGV

Aquí hay una explicación:

  • x #. yinterpreta el vector entero ycomo un xnúmero base ; por ejemplo, 10 #. 1 2 3 4rendimientos 1234.
  • u invproduce el inverso de un verbo u. En particular, x #. inv yrepresenta ycomo un xnúmero base ; por ejemplo,10 #. 1234 rendimientos 1 2 3 4. Observe que invse define como ^:_1, es decir, uaplicado -1 veces.
  • x * yes el producto de xyy , por lo tanto, x 10&#.inv@* yproduce una representación en base 10 del producto de xy y.
  • x # ycopia el n -ésimo de yla frecuencia que el n -ésimo elemento de la x; cuando xes un vector de booleanos,x selecciona qué elementos ytomar. Por ejemplo, 1 0 1 0 # 1 2 3 4rendimientos 1 3.
  • * y produce el signum de y.
  • x u~ y es el reflejo de u, es decir, lo mismo que y u x.
  • Por lo tanto, y #~ * yproduce un vector de todos los elementos dey que son positivos. En notación tácita, esto se puede escribir con un gancho como (#~ *).
  • {: yproduce el último elemento en y.
  • reunidos juntos, obtenemos la frase tácita ([:{:@(#~*)10&#.inv@*).
  • u/ yes la reducción de y, es decir, el verbo diádico uinsertado entre elementos de y. Por ejemplo, +/1 2 3 4es como1 + 2 + 3 + 4 y rinde 10.
  • Así, la frase ([:{:@(#~*)10&#.inv@*)/ y produce el último dígito del producto de los elementos de y.
  • ARGV es un vector en caja de los argumentos de la línea de comando.
  • ".>{:ARGV es el último argumento sin caja e interpretado como un número.
  • i. ycalcula números naturales de 0a y - 1.
  • Por lo tanto, 1+i. yproduce números naturales de 1a y. También podría haber usado el >: incremento aquí, pero 1+es más claro al mismo costo de los personajes.
  • Todo el programa simplemente se aplica 1+i.".>{:ARGV(el vector del 1número en el último argumento de la línea de comando) al verbo ([:{:@(#~*)10&#.inv@*)/e imprime el resultado con echo.
FUZxxl
fuente
1

Pyt , 5 bytes

!₫ą0⦋

Explicación:

         Implicit input (n)
!        n!
 ₫       Reverse the digits of (n!) - this disregards leading zeroes after reversal
  ą      Convert to array of digits
   0⦋    Get the first element

Pruébalo en línea!

mudkip201
fuente
1

R , 63 55 51 46 bytes

Calcula factorial, extrae el último dígito distinto de cero. Gracias a Giuseppe por proporcionar la estructura básica.

(y=(gamma(scan()+1))%/%10^(0:1e5)%%10)[!!y][1]

Pruébalo en línea!

Alternativamente, mi vieja respuesta de 51 bytes:

Calcula factorial, convierte a carácter, elimina todos los 0s, y luego toma el carácter final. Guardado 2 bytes gracias a Giuseppe.

substring(x<-gsub("0","",gamma(scan())+1),nchar(x))

Pruébalo en línea!

rturnbull
fuente
1
gamma(x+1) es más corto que factorial(x)
Giuseppe
sin conversión de cadena, lo mejor que conseguí fue (y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]en 54 bytes.
Giuseppe
@Giuseppe Podemos reemplazar nchar(x)con 1e5una solución de 46 bytes! Bien hecho.
rturnbull
1

> <> , 25 bytes

v:a%:?n-a,!
1
>$::?!.1-}*

Pruébalo en línea!

Maneja 0! correctamente también Valor pasado a través de la -vbandera.

Jo King
fuente
El caso de prueba 1000no produce ningún resultado en TIO, ¿qué pasa?
Toby Speight
1

Perl 6 ,  26  35 bytes

{[*](1..$_)~~/.*<(<-[0]>/}

Intentalo


Como un programa completo:

put [*](1..@*ARGS[0])~~/.*<(<-[0]>/

Intentalo

Expandido:

{
  [*]( 1..$_ ) # reduce using &infix:« * »
  ~~           # match with
  /
    .*         # any number of values (so it matches from the end)
    <(         # only capture the following
    <-[0]>     # any value but 0 (negated character class)
  /
}
Brad Gilbert b2gills
fuente
1

C (gcc) , 72 bytes (función)

f(n,d)long long n,d;{for(d=1;n;d%=10000)for(d*=n--;d%10<1;d/=10);d%=10;}

Pruébalo en línea!

C (gcc) , 101 99 bytes (programa completo)

main(){long long n,d=1;for(scanf("%lld",&n);n;d%=10000)for(d*=n--;d%10<1;d/=10);printf("%d",d%10);}

Pruébalo en línea!

Esta pregunta tiene apenas 8 años, por lo que "máquina razonable" no es lo mismo que en aquel entonces, pero obtengo tiempos de ~ .01 segundos en mi computadora cuando hago todos los casos de prueba juntos, así que a menos que las computadoras hayan aumentado su velocidad por un factor de 1000 en esta última década, debería estar bien.

gastropner
fuente
La ley de Moore todavía está (un poco) vigente, por lo que debería ser aproximadamente 16 veces más rápido
solo ASCII el
Además, una función está bien
solo ASCII el
0

Adjunto , 26 bytes

Last@`\&:(All@V)@Digits@`!

Pruébalo en línea!

Explicación

Last@`\&:(All@V)@Digits@`!

Esta es una composición de 4 funciones:

  • `! - esta es una versión funcional del operador factorial
  • Digits - esto obtiene los dígitos del factorial
  • \&:(All@V)- Esta es una función de selección. Funciona mediante la unión a la izquierda ( &:) la función All@Va \que se seleccione. A su vez, All@Ves una forma corta de probar si un número no es 0. Funciona al enviar su entrada a un vector0 -> [0] luego preguntar si todos esos miembros son verdaderos (es decir, no 0). Esto da los dígitos del número sin ceros.
  • Last - esto simplemente obtiene el último miembro de esta matriz.
Conor O'Brien
fuente
Esto parece increíblemente lento: el TIO agotó el tiempo de espera (1 minuto) en el caso de prueba 100000: ¿cómo obtuvo el resultado 1000000 en 10 segundos?
Toby Speight
@TobySpeight Cuando respondí a este desafío, ese requisito en particular no estaba allí (verifique el historial de revisiones).
Conor O'Brien
¡Ah, debería haber mirado la historia! Sin embargo, ¿verificó todos los casos de prueba en la pregunta?
Toby Speight
Parece que hubo una gran cantidad de respuestas durante el período en que se eliminó el límite de tiempo de la pregunta; eso es lamentable, de verdad.
Toby Speight
@TobySpeight Sí, lo hice. Es lamentable, y no estoy seguro de la política al respecto.
Conor O'Brien
0

APL (Dyalog Unicode) , 18 15 bytes

{⊢/⍵/⍨0≠⍎¨⍵}⍕∘!

Pruébalo en línea!

Función de prefijo tácito. Devuelve el dígito correcto para un solo caso de prueba, o una cadena de dígitos para múltiples casos de prueba.

Gracias a @ Adám y @ErikTheOutgolfer por 3 bytes cada uno.

¿Cómo?

{⊢/⍵/⍨0≠⍎¨⍵}⍕∘!  Main function. Argument is a number following the !.
              !  Factorial
                then
                Format (stringify)
        ⍎¨⍵}     Execute (turn to number) each digit of the argument
      0         Check if each is 0. This returns a boolean vector
                Swap arguments for the following fn/op
   ⍵/            Replicate. This takes a boolean vector as left arg and returns the truthy elements of the right arg. E.g.: 1 1 0/1 2 3  1 2.
{⊢/              Reduce. This returns the rightmost (last) element of a vector argument.
J. Sallé
fuente
0

NARS APL, 28 bytes, 14 caracteres

{↑≠v/v←⌽⍎¨⍕!⍵}

No sé por qué, pero esto pasa la prueba:

  q←{↑≠v/v←⌽⍎¨⍕!⍵}       
  q¨1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 6 4 2 2 4 2 8 8 8 6 8 2 
RosLuP
fuente
0

AWK , 47 57 bytes

{for(p=$1;--$1;p=(p*$1)%1e4)while(!(p%10))p/=10;$0=p%10}1

Pruébalo en línea!

La solución original no manejó muy bien los valores de entrada "grandes". Podría agregarse -Mpara forzarlo a funcionar, pero eso también requiere mucho más tiempo de procesamiento.

Robert Benson
fuente
Sí, @TobySpeight, infno %muy bien. :(
Robert Benson
Ah ... mirando la versión de la pregunta que respondí, no se requerían grandes números.
Robert Benson
-2

Japt , 6 bytes

Se me ocurrieron algunos 6 bytes diferentes, pero este me gustó más. Sin embargo, estoy convencido de que debe haber una manera de hacerlo en 5.

Êsw ìv

Intentalo


Explicación

Êcalcula el factorial de la entrada, lo sconvierte en una cadena y vuelve a un número entero después de whaberlo invertido, ìconvierte el resultado en una matriz de dígitos y vdevuelve el primer elemento.


Alternativas

Êì w æ
ÊìÈf Ì
Êì f o
Êsw sg
Êìf ìo
Êìf ìÌ
Lanudo
fuente
¿Cuánto tiempo lleva esto ejecutar todos los casos de prueba?
Toby Speight
@TobySpeight; eso es muy fácil de probar siguiendo el enlace para probarlo. Tenga en cuenta que los últimos 4 casos de prueba fallarán ya que sus factoriales son más grandes que el entero máximo de JavaScript.
Shaggy
Entonces, ¿en realidad no resuelve el problema? La pregunta dice que debe tener éxito durante 1 ≤ N ≤ 1,000,000 . Otras respuestas demuestran que no es necesario poder almacenar el factorial para calcular la respuesta.
Toby Speight
Probé la prueba en línea, pero se agotó el tiempo en el primer caso de prueba que probé (1000).
Toby Speight
-2

Perl 5 , 36 + 10 ( -p -Mbigint) = 46 bytes

$"=$_;$_*=$"while$"-=1;($_)=/(.)0*$/

Pruébalo en línea!

Xcali
fuente
La versión TIO falla los dos primeros casos de prueba que probé: 1000000 ⇒ f(debería ser 4 ) y 100 ⇒ 7(debería ser 4 )
Toby Speight
Está desbordando el tamaño de un int. La nueva versión funciona utilizando bigint. El rendimiento todavía deja algo que desear, ya que es un cálculo de fuerza bruta. Eso significa que se agota el tiempo de espera en TIO para números más grandes.
Xcali