Último dígito diferente de zero de n!

22

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 portanto o código mais curto em bytes vence!

fR0DDY
fonte
Função única ou programa completo?
Joey
@ joey Não, são apenas casos de teste. Entrada única, saída única.
FR0DDY
@joey Programa completo.
FR0DDY
1
Exigência de um programa completo é desencorajado ...
Erik o Outgolfer
2
@EriktheOutgolfer isto é de ~ 7 anos atrás, então eu não acho que foi determinada no momento
NoOneIsHere

Respostas:

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}

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
Dogbert
fonte
11

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.

Martin Ender
fonte
1
O Mathematica é praticamente a linguagem perfeita para esta pergunta.
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
fonte
3

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]]
Charles
fonte
2

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.
Joey
fonte
2

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.


fonte
2

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.

aditsu
fonte
2

Mathematica, 34 bytes

Mod[#!/10^IntegerExponent[#!],10]&
alefalpha
fonte
2

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
Kaldo
fonte
1
A versão do TIO atingiu o tempo limite (60s) no último caso de teste - como você conseguiu em 10s uma "máquina razoável"?
precisa
2

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.

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

Experimente online!

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

rochascientista
fonte
Bem-vindo ao PPCG! Bom primeiro post! Espero que você fique por aqui!
Rɪᴋᴇʀ
Bem-vindo ao PPCG! Concordo com o @Riker, ótimo primeiro post. Muito bem, jogando meu código combinando os loops. Você pode jogar mais 1 byte na sua resposta atual substituindo ||por |e um byte adicional substituindo ==0por <1. Aproveite sua estadia!
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 é 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):

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.

Toby Speight
fonte
1
Pode ser interessante notar que 2147483647!tem mais de 19 bilhões de dígitos e (2^63-1)!mais de 170.000.000.000.000.000.000.000 de dígitos, portanto, essa é uma grande vitória sobre o cálculo dos fatoriais. 1000000!conforme especificado na pergunta, é possível calcular o hardware atual; são apenas 5,5 milhões 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";}

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

Arnaud Le Blanc
fonte
1

Python3

239 Chars

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

299 caracteres (um pouco mais 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
fonte
1

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).

stusmith
fonte
Salve dois caracteres, substitua foldl1por product(cf codegolf.stackexchange.com/questions/607/find-the-factorial/… ). Mas você já tentou com 1000000! ?
JB
PS: não é um programa completo.
JB
Desculpe, fiz isso antes disso foi esclarecido nos comentários. Vou atualizá-lo.
stusmith
1

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.
FUZxxl
fonte
1

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!

mudkip201
fonte
1

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!

rturnbull
fonte
1
gamma(x+1)é menor quefactorial(x)
Giuseppe
sem a conversão de string, o melhor que consegui obter foi (y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]em 54 bytes.
Giuseppe
@Giuseppe Podemos substituir nchar(x)com 1e5uma solução de 46 bytes! Boa viagem.
rturnbull
1

> <> , 25 bytes

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

Experimente online!

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

Brincadeira
fonte
O caso de teste 1000não produz nenhuma saída no TIO - o que há de errado?
Toby Speight
1

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)
  /
}
Brad Gilbert b2gills
fonte
1

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.

gastropner
fonte
A lei de Moore ainda está (meio que) aguentando, então deve ser cerca de 16 vezes mais rápida
somente ASCII
Além disso, uma função é boa
somente ASCII
0

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.
Conor O'Brien
fonte
Isso parece incrivelmente lento - o TIO atingiu o tempo limite (1 minuto) no caso de teste 100000 - como você obteve o resultado 1000000 em 10 segundos?
precisa
@TobySpeight Quando eu respondi a esse desafio, esse requisito específico não estava lá (verifique o histórico de revisões).
Conor O'Brien
Ah, eu deveria ter olhado para a história! Você verificou todos os casos de teste da pergunta?
precisa
Parece que houve uma enxurrada de respostas durante o período em que o prazo foi removido da pergunta - isso é realmente lamentável.
precisa
@TobySpeight Sim, eu fiz. É lamentável, e não tenho certeza da política em relação a isso.
Conor O'Brien
0

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.
J. Sallé
fonte
0

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 
RosLuP
fonte
0

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.

Robert Benson
fonte
Sim, @TobySpeight, infnão está %muito bem. :(
Robert Benson
Ah ... olhando para a versão da pergunta que respondi, não eram necessários grandes números.
Robert Benson
-2

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 ìÌ
Shaggy
fonte
Quanto tempo leva para executar todos os casos de teste?
Toby Speight
@TobySpeight; é muito fácil testar seguindo o link para experimentá-lo. Observe que os últimos 4 casos de teste falharão, pois seus fatoriais são maiores que o número máximo máximo do JavaScript.
Shaggy
Então, na verdade, não resolve o problema? A pergunta diz que deve ter sucesso para 1 ≤ N ≤ 1.000.000 . Outras respostas demonstram que você não precisa armazenar o fatorial para calcular a resposta.
Toby Speight
Eu tentei o teste online, mas o tempo limite expirou no primeiro caso de teste que experimentei (1000).
Toby Speight
-2

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

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

Experimente online!

Xcali
fonte
A versão TIO falhar os dois primeiros casos de teste que eu tentei: 1000000 ⇒ f(deve ser 4 ) e 100 ⇒ 7(deve ser 4 )
Toby Speight
Está transbordando o tamanho de um int. A nova versão funciona usando bigint. O desempenho ainda deixa algo a desejar, pois é um cálculo de força bruta. Isso significa que o tempo limite é excedido no TIO para números maiores.
Xcali