Digit n-nol terakhir!

22

Diberikan bilangan bulat 1 ≤ N ≤ 1.000.000 sebagai input, menghasilkan digit N -nol terakhir ! , Di mana ! adalah faktorial (produk dari semua angka dari 1 hingga N , inklusif). Ini adalah urutan OEIS A008904 .

Program Anda perlu selesai dalam waktu 10 detik pada mesin yang masuk akal untuk input yang valid.

Uji Kasus

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

Ini adalah sehingga kode terpendek dalam byte menang!

fR0DDY
sumber
Fungsi tunggal atau program lengkap?
Joey
@ Joey Tidak, mereka hanya kasus uji. Input Tunggal, Output Tunggal.
fR0DDY
@ joey Selesaikan program.
fR0DDY
1
Persyaratan untuk program lengkap tidak disarankan ...
Erik the Outgolfer
2
@EriktheOutgolfer ini dari ~ 7 tahun yang lalu, jadi saya tidak berpikir yang ditentukan saat itu
NoOneIsHere

Jawaban:

8

Ruby - 63 karakter

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}

Sumber - http://oeis.org/A008904

Menangani hingga seribu digit di bawah satu detik.

Uji

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
sumber
11

Mathematica, 45 36 byte

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

Sangat mudah dibaca untuk jawaban yang menang. :) (Kemudian lagi, belum ada pengiriman GolfScript & Co.)

Ini menangani input 1.000.000 dalam waktu sekitar 5 detik pada mesin saya.

Martin Ender
sumber
1
Mathematica adalah bahasa yang cukup sempurna untuk pertanyaan ini.
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
sumber
3

PARI / GP - 27 byte

Ini memperdagangkan kecepatan untuk ukuran - testcase membutuhkan waktu lama (~ 6 detik).

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

Versi ini jauh lebih cepat (~ 15 mikrodetik) tetapi membutuhkan 81 byte:

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)

Anda dapat menggunakan kode (non-golf) ini untuk menguji:

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

Windows PowerShell, 53 56 59 60 63 73 90

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

Catatan:

  • Memakan waktu lebih lama dari satu menit untuk angka mendekati 100.000. Namun, menghapus nol pada akhirnya membutuhkan konversi ke string, melakukan perhitungan membutuhkan angka, sehingga konversi tidak dapat dihindari dalam hal apa pun.

Sejarah:

  • 2011-02-08 10:31 (90) - Upaya pertama.
  • 2011-02-08 10:33 (73) - Modulus lebih pendek dari memotong dan bergabung.
  • 2011-02-08 10:34 (63) - Potong tidak perlu.
  • 2011-02-08 10:37 (60) - Tidak perlu dilemparkan ke nomor. Modulus sudah cukup, sudah.
  • 2011-02-08 10:40 (59) - Beberapa inlining.
  • 2011-02-08 11:00 (56) - Apa yang saya katakan sebelumnya tentang modulus lebih pendek? Berlaku untuk output juga.
  • 2011-02-08 11:01 (53) - Casting $inputke string sudah cukup; para pemeran intditerapkan secara implisit.
Joey
sumber
2

Perl, 53 58 61 karakter

Semua spasi putih dapat dihapus, tetapi saya meninggalkannya untuk "keterbacaan". Catatan: tidak menggunakan rumus eksplisit konyol dari Sloane.

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

Menghitung f (10 ^ 6) dalam 8,7 detik pada mesin saya.

Pembaruan : OP menginginkannya menjadi keseluruhan program:

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

Itu membuatnya menjadi 55 karakter.


sumber
2

CJam - 28

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

Anda dapat mencobanya di http://cjam.aditsu.net/ untuk nilai hingga 10.000 atau lebih; untuk angka yang lebih besar Anda harus menggunakan penerjemah java . 1000000 berjalan dalam waktu sekitar 3 detik di laptop saya.

Penjelasan:

Sayangnya solusi langsung terlalu lambat, jadi saya hanya menyimpan 7 digit terakhir (sebelum nol akhir) setelah setiap perkalian.

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

Catatan: bahasa ini jauh lebih baru daripada pertanyaan.

aditsu
sumber
2

Mathematica, 34 byte

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

05AB1E , 4 byte

!0м¤

Cobalah online!

Penjelasan

!0    # Push the factorial of the input and 0
  м   # Remove the occurences of 0 in the factorial
   ¤  # Push the last element, implicit display
Kaldo
sumber
1
Versi TIO kehabisan waktu (60 detik) pada test case terakhir - bagaimana Anda mendapatkannya dalam 10 detik pada "mesin masuk akal"?
Toby Speight
2

Jelly , 4 byte

!Ṛȯ/

Cobalah online!

Penjelasan

Menggunakan fakta bahwa ketika (membalikkan daftar; tidak membuat vektor)) diterapkan ke integer secara otomatis mengambil D(digit) terlebih dahulu.

Dengan input 8:

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

Saya tidak berpikir ada satu byte "elemen kebenaran pertama" (yang ȯ/bertindak sebagai) tetapi jika ada maka ini dapat dipersingkat menjadi tiga byte total.

dylnan
sumber
2

Java (OpenJDK 8) , 62 byte

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

Cobalah online!

Mirip dengan @Kevin Cruijssen tetapi menghemat 5 byte dengan menggabungkan loop.

ilmuwan batuan
sumber
Selamat datang di PPCG! Posting pertama yang bagus! Semoga kamu tetap disini!
Rɪᴋᴇʀ
Selamat datang di PPCG! Saya setuju dengan @Riker, posting pertama yang bagus. Dilakukan dengan baik golf kode saya dengan menggabungkan loop. Anda dapat memasukkan 1 byte lebih banyak jawaban Anda saat ini dengan mengganti ||dengan |, dan byte tambahan dengan mengganti ==0dengan <1. Selamat menikmati!
Kevin Cruijssen
2

C, 150 140 135 byte

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

Ini adalah versi untuk sistem ASCII; ganti string 33436dengan 11214untuk sistem EBCDIC, atau dengan \1\1\2\1\4untuk program portabel.

Solusi C agak terhambat oleh persyaratan untuk menyediakan program lengkap; Namun, ini menjawab pertanyaan sepenuhnya.

Cobalah online (memerlukan Javascript):

Penjelasan

Ini didasarkan pada algoritma yang digariskan dalam Least Significant Non-Zero Digit of n! , berbalik sehingga kita kembali untuk menemukan kekuatan tertinggi lima, dan melakukan perhitungan di jalan keluar. Tabel konstanta terlalu besar, jadi saya menguranginya dengan menemukan hubungan antara residu sebelumnya r, digit saat ini ddan kedalaman rekursi 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

Sebab r>0, ini menyelesaikan ke kali rkali konstan 2^dk(mod 5); konstanta ada di a[]bawah (sebaris dalam kode golf). Kami juga mengamati bahwa itu (2^4)%5adalah 1, sehingga kami dapat mengurangi eksponen untuk menghindari meluapnya kisaran 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 */
}

Tes:

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

Performanya juga terhormat. Berikut input maksimum untuk sistem dengan 32-bit int:

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

Saya mendapat timing yang sama dengan 64-bit maksimal intjuga.

Toby Speight
sumber
1
Mungkin menarik untuk dicatat bahwa 2147483647!memiliki lebih dari 19 miliar digit, dan (2^63-1)!lebih dari 170.000.000.000.000.000.000 digit, jadi ini adalah kemenangan besar atas perhitungan faktorial. 1000000!sebagaimana ditentukan dalam pertanyaan layak untuk dihitung pada perangkat keras saat ini; itu hanya 5½ juta digit. :-)
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";}

Berjalan di bawah 10 detik dengan testcase yang diberikan.

Arnaud Le Blanc
sumber
1

Python3

239 Chars

Dapat melakukan 10000 dalam ~ 3,2 detik (Ideone memotong saya pada 8 detik, saya yakin itu akan memakan waktu lebih dari 10 detik :()

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 Chars (sedikit lebih cepat)

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
sumber
1

Haskell, 78 karakter

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

(Mungkin perlu dikompilasi untuk menghitung 1.000.000! Dalam 10 detik).

tukang kayu
sumber
Simpan dua karakter, ganti foldl1dengan product(cf codegolf.stackexchange.com/questions/607/find-the-factorial/… ). Tetapi apakah Anda benar-benar mencoba dengan 1000000! ?
JB
PS: bukan program yang lengkap.
JB
Maaf, apakah sebelum itu telah diklarifikasi dalam komentar. Saya akan memperbaruinya.
stusmith
1

J - 42 40 karakter

Seluruh program. Simpan program ini dalam file dan jalankan jconsole script.ijs 1234. Perhatikan bahwa program ini tidak keluar dari juru bahasa setelah mencetak hasilnya. Ketik ^Datau exit]0untuk keluar dari juru bahasa.

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

Berikut ini penjelasannya:

  • x #. ymenafsirkan vektor bilangan bulat ysebagai angka dasar x; misalnya, 10 #. 1 2 3 4hasil 1234.
  • u invmenghasilkan kebalikan dari kata kerja u. Secara khusus, x #. inv ymewakili ysebagai xnomor dasar ; misalnya, 10 #. 1234hasil 1 2 3 4. Perhatikan bahwa invdidefinisikan sebagai ^:_1, yaitu, uditerapkan -1 kali.
  • x * yadalah produk dari xdan y, dengan demikian x 10&#.inv@* ymenghasilkan representasi basis-10 dari produk xdan y.
  • x # ymenyalin item ke- ny sesering item ke- n dari x; kapan xvektor boolean, xpilih item mana yang yakan diambil. Misalnya, 1 0 1 0 # 1 2 3 4hasil 1 3.
  • * ymenghasilkan signum dari y.
  • x u~ yadalah refleksif dari u, yaitu, sama dengan y u x.
  • Dengan demikian, y #~ * yhasilkan vektor semua item yyang positif. Dalam notasi diam-diam, ini dapat ditulis dengan kait sebagai (#~ *).
  • {: ymenghasilkan item terakhir dalam y.
  • berkumpul bersama, kita mendapatkan frasa diam-diam ([:{:@(#~*)10&#.inv@*).
  • u/ yadalah reduksi dari y, yaitu, kata kerja diad udimasukkan di antara elemen y. Misalnya, +/1 2 3 4seperti 1 + 2 + 3 + 4dan hasil 10.
  • Dengan demikian, frasa ([:{:@(#~*)10&#.inv@*)/ ymenghasilkan digit terakhir dari produk item y.
  • ARGV adalah kotak vektor dari argumen baris perintah.
  • ".>{:ARGV adalah argumen terakhir tanpa kotak dan ditafsirkan sebagai angka.
  • i. ymenghitung bilangan asli dari 0hingga y - 1.
  • Jadi, 1+i. ymenghasilkan bilangan asli dari 1hingga y. Saya bisa juga menggunakan >: increment di sini, tetapi 1+lebih jelas dengan biaya karakter yang sama.
  • Seluruh program hanya berlaku 1+i.".>{:ARGV(vektor 1ke nomor dalam argumen baris perintah terakhir) ke kata kerja ([:{:@(#~*)10&#.inv@*)/dan mencetak hasilnya dengan echo.
FUZxxl
sumber
1

Pyt , 5 byte

!₫ą0⦋

Penjelasan:

         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

Cobalah online!

mudkip201
sumber
1

R , 63 55 51 46 byte

Hitung faktorial, ekstrak angka non-nol terakhir. Terima kasih kepada Giuseppe karena menyediakan struktur dasar.

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

Cobalah online!

Atau, jawaban lama 51 byte saya:

Menghitung faktorial, mengkonversi ke karakter, menghapus semua 0s, dan kemudian mengambil karakter terakhir. Disimpan 2 byte berkat Giuseppe.

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

Cobalah online!

rturnbull
sumber
1
gamma(x+1)lebih pendek darifactorial(x)
Giuseppe
tanpa konversi string, yang terbaik yang saya dapatkan adalah (y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]54 byte.
Giuseppe
@ Giuseppe Kita dapat mengganti nchar(x)dengan 1e5untuk solusi 46-byte! Bagus sekali.
rturnbull
1

> <> , 25 byte

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

Cobalah online!

Pegangan 0! dengan benar juga. Nilai melewati -vbendera.

Jo King
sumber
Kasing uji 1000tidak menghasilkan keluaran apa pun pada TIO - apa yang salah?
Toby Speight
1

Perl 6 ,  26  35 byte

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

Cobalah


Sebagai program lengkap:

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

Cobalah

Diperluas:

{
  [*]( 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
sumber
1

C (gcc) , 72 byte (fungsi)

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

Cobalah online!

C (gcc) , 101 99 byte (seluruh program)

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

Cobalah online!

Pertanyaan ini hanya berumur 8 tahun sehingga "mesin yang masuk akal" tidak sama dengan waktu itu, tapi saya mendapatkan waktu ~ 0,01 detik di komputer saya ketika melakukan semua kasus uji bersama, jadi kecuali komputer telah meningkatkan kecepatannya dengan faktor 1000 dekade terakhir ini, itu harus baik-baik saja.

gastropner
sumber
Hukum Moore masih (agak) bertahan, jadi itu harus sekitar x16 kali lebih cepat
ASCII-satunya
Juga, sebuah fungsi baik
hanya ASCII
0

Attache , 26 byte

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

Cobalah online!

Penjelasan

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

Ini adalah komposisi dari 4 fungsi:

  • `! - ini adalah versi fungsional dari operator faktorial
  • Digits - ini mendapatkan angka dari faktorial
  • \&:(All@V)- Ini adalah fungsi pemilihan. Ini bekerja dengan ikatan kiri ( &:) fungsiAll@V untuk \, yang dipilih. Pada gilirannya, All@Vini adalah cara singkat untuk menguji apakah suatu bilangan bukan 0. Ia bekerja dengan memasukkan inputnya ke sebuah vektor 0 -> [0]kemudian menanyakan apakah semua anggota itu benar (yaitu bukan 0). Ini memberikan digit angka tanpa 0s.
  • Last - ini hanya mendapatkan anggota terakhir dari array ini.
Conor O'Brien
sumber
Ini tampaknya sangat lambat - TIO kehabisan waktu (1 menit) pada 100000 test case - bagaimana Anda mendapatkan hasil 1000000 dalam 10 detik?
Toby Speight
@TobySpeight Ketika saya menjawab tantangan ini, persyaratan khusus itu tidak ada di sana (periksa riwayat revisi).
Conor O'Brien
Ah, aku seharusnya melihat sejarah! Anda memang memverifikasi semua testcases dalam pertanyaan?
Toby Speight
Tampaknya ada banyak jawaban selama periode tersebut sehingga batas waktu telah dihapus dari pertanyaan - sungguh disayangkan.
Toby Speight
@TobySpeight Ya, saya lakukan. Sangat disayangkan, dan saya tidak yakin dengan kebijakan tentang ini.
Conor O'Brien
0

APL (Dyalog Unicode) , 18 15 byte

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

Cobalah online!

Fungsi awalan Tacit. Mengembalikan digit yang benar untuk satu test case, atau serangkaian digit untuk beberapa test case.

Terima kasih kepada @ Adám dan @ErikTheOutgolfer untuk masing-masing 3 byte.

Bagaimana?

{⊢/⍵/⍨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é
sumber
0

APL NARS, 28 byte, 14 karakter

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

Saya tidak tahu mengapa tetapi ini lulus ujian:

  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
sumber
0

AWK , 47 57 byte

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

Cobalah online!

Solusi asli tidak menangani nilai input "besar" dengan sangat baik. Dapat menambah -Muntuk memaksanya bekerja, tetapi itu juga membutuhkan lebih banyak waktu pemrosesan.

Robert Benson
sumber
Ya, @TobySpeight, inftidak %begitu baik. :(
Robert Benson
Ah ... melihat versi dari pertanyaan yang saya jawab, sejumlah besar tidak diperlukan.
Robert Benson
-2

Japt , 6 byte

Datang dengan 6-byters berbeda tapi saya suka yang terbaik ini. Tapi saya yakin pasti ada cara untuk melakukannya dalam 5 menit.

Êsw ìv

Cobalah


Penjelasan

Êmenghitung faktorial dari input, smengubahnya menjadi string dan kembali ke integer setelah wmembalikkannya, ìmengubah hasilnya menjadi array angka dan vmengembalikan elemen pertama.


Alternatif

Êì w æ
ÊìÈf Ì
Êì f o
Êsw sg
Êìf ìo
Êìf ìÌ
Shaggy
sumber
Berapa lama waktu yang dibutuhkan untuk menjalankan semua kasus uji?
Toby Speight
@TobySpeight; itu sangat mudah untuk diuji dengan mengikuti tautan untuk mencobanya. Perhatikan bahwa 4 kasus uji terakhir akan gagal karena faktorialnya lebih besar dari integer maks JavaScript.
Shaggy
Jadi itu sebenarnya tidak menyelesaikan masalah? Pertanyaannya mengatakan itu harus berhasil untuk 1 ≤ N ≤ 1.000.000 . Jawaban lain menunjukkan bahwa Anda tidak perlu menyimpan faktorial untuk menghitung jawabannya.
Toby Speight
Saya mencoba tes online, tetapi gagal pada test-case pertama yang saya coba (1000).
Toby Speight
-2

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

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

Cobalah online!

Xcali
sumber
Versi TIO gagal dalam dua uji kasus pertama yang saya coba: 1000000 ⇒ f(harus 4 ) dan 100 ⇒ 7(harus 4 )
Toby Speight
Ini meluap ukuran int. Versi baru berfungsi dengan menggunakan bigint. Kinerja masih menyisakan sesuatu yang diinginkan karena ini merupakan perhitungan brute force. Itu berarti keluar pada TIO untuk angka yang lebih besar.
Xcali