Dado um número inteiro 1 ≤ N ≤ 1.000.000 como entrada, imprima o último dígito diferente de zero de N! onde ! é o fatorial (o produto de todos os números de 1 a N , inclusive). Esta é a sequência OEIS A008904 .

Seu programa precisa terminar em 10 segundos em uma máquina razoável para qualquer entrada válida.

Casos de teste

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 é um código de golfe, portanto o código mais curto em bytes vence!

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}

Fonte - http://oeis.org/A008904

Alças de até mil dígitos em menos de um segundo.

Teste

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

Mathematica, 45 36 bytes

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

Muito legível para uma resposta vencedora. :) (Por outro lado, ainda não há envios da GolfScript & Co.).

Isso lida com a entrada 1.000.000 em cerca de 5 segundos na minha máquina.

Python - 75

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

PARI / GP - 27 bytes

Isso negocia velocidade por tamanho - o testcase leva muito tempo (~ 6 segundos).

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

Esta versão é muito mais rápida (~ 15 microssegundos), mas leva 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)

Você pode usar este código (sem golfe) para testar:

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

Windows PowerShell, 53 56 59 60 63 73 90

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

Notas:

• Leva mais de um minuto para um número próximo a 100.000. No entanto, remover zeros no final exige uma conversão em sequência, fazer cálculos exige um número, portanto as conversões são inevitáveis ​​em qualquer caso.

História:

• 08-02-2011 10:31 (90) - Primeira tentativa.
• 08-02-2011 10:33 (73) - O módulo é mais curto que cortar e unir.
• 08-02-2011 10:34 (63) - Corte desnecessário.
• 08-02-2011 10:37 (60) - Elenco desnecessário para um número. O Modulus já faz isso muito bem.
• 08-02-2011 10:40 (59) - Alguns inlining.
• 08-02-2011 11:00 (56) - O que eu disse antes sobre o módulo ser mais curto? Aplica-se também à saída.
• 08-02-2011 11:01 (53) - Fundir $inputuma corda é suficiente; o elenco para inté aplicado implicitamente.

Perl, 53 58 61 personagens

Todo o espaço em branco pode ser removido, mas eu o deixei para "legibilidade". Nota: não use alguma fórmula explícita boba de Sloane.

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

Calcula f (10 ^ 6) em 8,7 segundos na minha máquina.

Atualização : O OP queria que fosse um programa inteiro:

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

Isso torna 55 caracteres.

CJam - 28

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

Você pode experimentá-lo em http://cjam.aditsu.net/ para valores de até 10000; para números maiores, você deve usar o interpretador java . 1000000 é executado em cerca de 3 segundos no meu laptop.

Explicação:

Infelizmente, a solução direta é muito lenta, por isso estou mantendo apenas os últimos 7 dígitos (antes dos zeros à direita) após cada multiplicação.

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: esse idioma é muito mais recente que a pergunta.

Mathematica, 34 bytes

Mod[#!/10^IntegerExponent[#!],10]&

05AB1E , 4 bytes

!0м¤

Experimente online!

Explicação

!0    # Push the factorial of the input and 0
  м   # Remove the occurences of 0 in the factorial
   ¤  # Push the last element, implicit display

Gelatina , 4 bytes

!Ṛȯ/

Experimente online!

Explicação

Usa o fato de que, quando Ṛ(reverter uma lista; não vetoriza) é aplicado a um número inteiro, ele automaticamente leva D(dígitos) primeiro.

Com a entrada 8:

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

Eu não acho que exista um "primeiro elemento de verdade" de um byte (que ȯ/atua como), mas se houver, pode ser reduzido para três bytes no total.

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;}

Experimente online!

Semelhante ao @ Kevin Cruijssen, mas economiza 5 bytes combinando os loops.

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 é a versão para sistemas ASCII; substituir a cadeia 33436com 11214um sistema EBCDIC, ou com \1\1\2\1\4um programa portátil.

As soluções C são um pouco dificultadas pelo requisito de fornecer um programa completo; no entanto, isso responde totalmente à pergunta.

Experimente online (requer Javascript):

• Apenas 1000000
• Loop com todos os casos de teste

Explicação

É baseado no algoritmo descrito em Dígito não zero menos significativo de n! , virou-se para que recuássemos para encontrar a potência mais alta de cinco e faça o cálculo na saída. As tabelas de constantes eram muito grandes, então reduzi-as encontrando uma relação entre o resíduo anterior r, o dígito atual de a profundidade da recursão 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

Pois r>0isso se resolve com tempos de rtempos constantes 2^dk(mod 5); as constantes estão a[]abaixo (destacadas no código do golfe). Também observamos que (2^4)%5é 1, para que possamos reduzir o expoente para evitar transbordar o intervalo 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 */
}

Testes:

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

O desempenho também é respeitável. Aqui está uma entrada máxima para um sistema com 32 bits int:

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

Também obtive os mesmos tempos com um máximo de 64 bits int.

PHP - 105

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

Executa menos de 10 segundos com o caso de teste fornecido.

Python3

Pode fazer 10000 em ~ 3,2 segundos (a Ideone me interrompe em 8 segundos, tenho certeza de que demorará mais 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

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)

Haskell, 78 caracteres

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

(Provavelmente precisaria ser compilado para calcular 1.000.000! Em 10 segundos).

J - 42 40 caracteres

Um programa inteiro. Salve este programa em um arquivo e execute com jconsole script.ijs 1234. Observe que este programa não sai do intérprete após a impressão de um resultado. Digite ^Dou exit]0para sair do intérprete.

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

Aqui está uma explicação:

• x #. yinterpreta o vetor inteiro ycomo um xnúmero base ; por exemplo, 10 #. 1 2 3 4produz 1234.
• u invproduz o inverso de um verbo u. Em particular, x #. inv yrepresenta ycomo um xnúmero base ; por exemplo, 10 #. 1234produz 1 2 3 4. Observe que invé definido como ^:_1, isto é, uaplicado -1 tempo.
• x * yé o produto de xe y, portanto, x 10&#.inv@* yproduz uma representação de base 10 do produto de xe y.
• x # ycopia o n- ésimo item ytantas vezes quanto o n- ésimo item de x; Quando xé um vetor de booleano, xseleciona quais itens ylevar. Por exemplo, 1 0 1 0 # 1 2 3 4produz 1 3.
• * yproduz o signum de y.
• x u~ yé o reflexo de u, isto é, o mesmo que y u x.
• Assim, y #~ * yproduz um vetor de todos os itens ypositivos. Em notação tácita, isso pode ser escrito com um gancho como (#~ *).
• {: yproduz o último item em y.
• reunidos, temos a frase tácita ([:{:@(#~*)10&#.inv@*).
• u/ yé a redução do yverbo diádico uinserido entre os elementos de y. Por exemplo, +/1 2 3 4é como 1 + 2 + 3 + 4e produz 10.
• Assim, a frase ([:{:@(#~*)10&#.inv@*)/ yproduz o último dígito do produto dos itens de y.
• ARGV é um vetor em caixa dos argumentos da linha de comando.
• ".>{:ARGV é o último argumento sem caixa e interpretado como um número.
• i. ycalcula números naturais de 0até y - 1.
• Assim, 1+i. yproduz números naturais de 1até y. Eu também poderia ter usado >: incremento aqui, mas 1+é mais claro ao mesmo custo de caracteres.
• O programa inteiro se aplica apenas 1+i.".>{:ARGV(o vetor de 1ao número no último argumento da linha de comando) ao verbo ([:{:@(#~*)10&#.inv@*)/e imprime o resultado com echo.

Pyt , 5 bytes

!₫ą0⦋

Explicação:

         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

Experimente online!

R , 63 55 51 46 bytes

Calcula fatorial, extrai o último dígito diferente de zero. Agradecimentos a Giuseppe por fornecer a estrutura básica.

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

Experimente online!

Como alternativa, minha antiga resposta de 51 bytes:

Calcula fatorial, converte em caractere, remove todos os 0se depois pega o caractere final. Economizou 2 bytes graças a Giuseppe.

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

Experimente online!

> <> , 25 bytes

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

Experimente online!

Alças 0! corretamente também. Valor transmitido pela -vbandeira.

Perl 6 ,  26  35 bytes

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

Tente

Como um programa completo:

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

Tente

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)
  /
}

C (gcc) , 72 bytes (função)

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

Experimente online!

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

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);}

Experimente online!

Essa pergunta tem apenas 8 anos e, portanto, "máquina razoável" não é a mesma de então, mas estou recebendo ~ 0,01 segundos no meu computador ao executar todos os casos de teste juntos, portanto, a menos que os computadores tenham aumentado a velocidade por um fator de 1000 na última década, deve estar bem.

Adicionar ++ , 11 bytes

L,RB*EDBFEZ

Experimente online!

Anexo , 26 bytes

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

Experimente online!

Explicação

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

Esta é uma composição de 4 funções:

• `! - esta é uma versão funcional do operador fatorial
• Digits - obtém os dígitos do fatorial
• \&:(All@V)- Esta é uma função de seleção. Ele funciona ligando à esquerda ( &:) a função All@Vto \, que é select. Por sua vez, All@Vé uma maneira curta de testar se um número não é 0. Ele funciona lançando sua entrada para um vetor0 -> [0] depois perguntando se todos esses membros são verdadeiros (ou seja, não são 0). Isso fornece os dígitos do número sem 0s.
• Last - isto simplesmente obtém o último membro desta matriz.

APL (Dyalog Unicode) , 18 15 bytes

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

Experimente online!

Função de prefixo tácito. Retorna o dígito correto para um único caso de teste ou uma sequência de dígitos para vários casos de teste.

Obrigado a @ Adám e @ErikTheOutgolfer por 3 bytes cada.

Quão?

{⊢/⍵/⍨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.

NARS APL, 28 bytes, 14 caracteres

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

Não sei por que, mas isso passa no teste:

  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 

AWK , 47 57 bytes

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

Experimente online!

A solução original não tratou muito bem os valores de entrada "grandes". Pode adicionar -Mpara forçá-lo a funcionar, mas isso também requer muito mais tempo de processamento.

Japonês , 6 bytes

Vim com alguns 6-byters diferentes, mas eu gostei mais deste. Estou convencido de que deve haver uma maneira de fazer isso em 5, no entanto.

Êsw ìv

Tente

Explicação

Êcalcula o fatorial da entrada, sconverte-o em uma sequência e depois em um número inteiro depois de a wreverter, ìconverte o resultado em uma matriz de dígitos e vretorna o primeiro elemento.

Alternativas

Êì w æ
ÊìÈf Ì
Êì f o
Êsw sg
Êìf ìo
Êìf ìÌ

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

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

Experimente online!