Последняя ненулевая цифра n!

22

Если в качестве входных данных задано целое число 1 ≤ N ≤ 1 000 000 , выведите последнюю ненулевую цифру N! где ! является факториалом (произведение всех чисел от 1 до N включительно). Это последовательность OEIS A008904 .

Ваша программа должна завершиться в течение 10 секунд на приемлемой машине для любого допустимого ввода.

Тестовые случаи

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

Это поэтому выигрывает самый короткий код в байтах!

fR0DDY
источник
Отдельная функция или полная программа?
Джои,
@ Joey Нет, они просто тестовые случаи. Один вход, один выход.
fR0DDY
@joey Завершить программу.
fR0DDY
1
Требование для полной программы не рекомендуется ...
Эрик Outgolfer
2
@EriktheOutgolfer это ~ 7 лет назад, так что я не думаю, что это было определено в то время
NoOneIsHere

Ответы:

8

Рубин - 63 символа

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}

Источник - http://oeis.org/A008904

Обрабатывает до тысячи цифр за секунду.

Тест

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
источник
11

Mathematica, 45 36 байт

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

Очень читабельный для победного ответа. :) (Опять же, пока еще нет заявки от GolfScript & Co.)

Это обрабатывает ввод 1 000 000 примерно за 5 секунд на моей машине.

Мартин Эндер
источник
1
Mathematica - почти идеальный язык для этого вопроса.
Майкл Стерн
4

Питон - 75

n=input()
g=1
while n:
 g*=n
 while g%10<1:g/=10
 g%=10**9
 n-=1
print g%10
JPvdMerwe
источник
3

PARI / GP - 27 байт

Это меняет скорость на размер - тестовый сценарий занимает много времени (~ 6 секунд).

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

Эта версия намного быстрее (~ 15 микросекунд), но занимает 81 байт:

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)

Вы можете использовать этот код (не для игры в гольф) для проверки:

[%(10^n) | n <- [1..6]]
Чарльз
источник
2

Windows PowerShell, 53 56 59 60 63 73 90

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

Заметки:

  • Занимает больше минуты для числа, близкого к 100 000. Однако удаление нулей в конце требует преобразования в строку, выполнение вычислений требует числа, поэтому преобразования в любом случае неизбежны.

История:

  • 2011-02-08 10:31 (90) - Первая попытка.
  • 2011-02-08 10:33 (73) - Модуль короче, чем нарезка и соединение.
  • 2011-02-08 10:34 (63) - Ненужная отделка салона.
  • 2011-02-08 10:37 (60) - Ненужное приведение к числу. Модуль делает это просто отлично, уже.
  • 2011-02-08 10:40 (59) - Немного врезки.
  • 2011-02-08 11:00 (56) - Что я говорил раньше о том, что модуль короче? Относится и к выходу.
  • 2011-02-08 11:01 (53) - достаточно бросить $inputв строку; приведение к intприменяется неявно.
детеныш
источник
2

Perl, 53 58 61 символы

Все пробелы могут быть удалены, но я оставил их для «читабельности». Примечание: не использовать какую-то глупую явную формулу от Слоана.

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

Вычисляет f (10 ^ 6) за 8,7 секунд на моей машине.

Обновление : OP хотел, чтобы это была целая программа:

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

Это делает его 55 символами.


источник
2

CJam - 28

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

Вы можете попробовать это на http://cjam.aditsu.net/ для значений до 10000 или около того; для больших чисел вы должны использовать Java-интерпретатор . 1000000 работает примерно на 3 секунды на моем ноутбуке.

Объяснение:

К сожалению, простое решение слишком медленное, поэтому я сохраняю только последние 7 цифр (перед конечными нулями) после каждого умножения.

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

Примечание: этот язык намного новее, чем вопрос.

aditsu
источник
2

Mathematica, 34 байта

Mod[#!/10^IntegerExponent[#!],10]&
alephalpha
источник
2

05AB1E , 4 байта

!0м¤

Попробуйте онлайн!

объяснение

!0    # Push the factorial of the input and 0
  м   # Remove the occurences of 0 in the factorial
   ¤  # Push the last element, implicit display
Kaldo
источник
1
Время ожидания версии TIO (60 с) в последнем тестовом примере - как вы получили ее за 10 с на «разумной машине»?
Тоби Спейт
2

Желе , 4 байта

!Ṛȯ/

Попробуйте онлайн!

объяснение

Использует тот факт, что когда (инвертировать список; не векторизовать) применяется к целому числу, оно автоматически берет D(цифры) в первую очередь.

С входом 8:

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

Я не думаю, что существует однобайтовый «первый истинный элемент» (который ȯ/действует как), но если он есть, его можно сократить до трех байтов.

dylnan
источник
2

Java (OpenJDK 8) , 62 байта

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

Попробуйте онлайн!

Похож на @Kevin Cruijssen, но экономит 5 байтов, комбинируя циклы.

rockscientist
источник
Добро пожаловать в PPCG! Хороший первый пост! Надеюсь, вы остаетесь вокруг!
Rɪᴋᴇʀ
Добро пожаловать в PPCG! Я согласен с @Riker, отличный первый пост. Хорошо сделано, играя в мой код, комбинируя петли. Вы можете добавить в свой текущий ответ еще 1 байт, заменив ||на |, и дополнительный байт, заменив ==0на <1. Приятного пребывания!
Кевин Круйссен,
2

C 150 140 135 байтов

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

Это версия для систем ASCII; замените строку 33436на 11214для системы EBCDIC или на \1\1\2\1\4для переносимой программы.

Решения C немного затруднены требованием предоставить полную программу; однако это полностью отвечает на вопрос.

Попробуйте онлайн (требуется Javascript):

объяснение

Он основан на алгоритме, описанном в наименее значимой ненулевой цифре n! Обернулся, чтобы мы вернулись, чтобы найти наибольшую силу пяти, и выполним расчет на выходе. Таблицы констант были слишком большими, поэтому я сократил их, найдя взаимосвязь между предыдущим остатком r, текущей цифрой dи глубиной рекурсии 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

Для r>0, это решает постоянные rвремена 2^dk(мод 5); константы указаны a[]ниже (указано в коде для игры в гольф). Мы также наблюдаем, что (2^4)%5это 1, поэтому мы можем уменьшить показатель степени, чтобы избежать переполнения диапазона 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 */
}

тесты:

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

Производительность тоже респектабельная. Вот максимальный вход для системы с 32-битным int:

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

Я получил те же тайминги с максимальной 64-битной intтоже.

Тоби Спейт
источник
1
Может быть интересно отметить, что в 2147483647!нем более 19 миллиардов цифр и (2^63-1)!более 170 000 000 000 000 000 000 цифр, так что это большой выигрыш в расчете факториалов. 1000000!как указано в вопросе возможно рассчитать на текущем оборудовании; это только 5 с половиной миллионов цифр. :-)
Тоби Спейт
1

PHP - 105

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

Запускается менее 10 секунд с данным тестовым сценарием.

Арно Ле Блан
источник
1

python3

239 символов

Может сделать 10000 за ~ 3,2 секунды (Ideone отключает меня за 8 секунд, но я уверен, что это займет больше времени, чем 10 секунд :()

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 символов (немного быстрее)

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
источник
1

Хаскель, 78 персонажей

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

(Вероятно, потребуется скомпилировать для вычисления 1 000 000! За 10 секунд).

Стусмит
источник
Сохраните два символа, замените их foldl1на product(см. Codegolf.stackexchange.com/questions/607/find-the-factorial/… ). Но вы действительно пробовали с 1000000! ?
JB
PS: не полная программа.
JB
Извините, сделал это до того, как было уточнено в комментариях. Я обновлю это.
Стусмит
1

J - 42 40 знаков

Целая программа. Сохраните эту программу в файле и запустите jconsole script.ijs 1234. Обратите внимание, что эта программа не выходит из интерпретатора после печати результата. Введите ^Dили, exit]0чтобы выйти из интерпретатора.

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

Вот объяснение:

  • x #. yинтерпретирует целочисленный вектор yкак базовое xчисло; например, 10 #. 1 2 3 4урожайность 1234.
  • u invдает инверсию глагола u. В частности, x #. inv yпредставляет yсобой базовое xчисло; например, 10 #. 1234урожайность 1 2 3 4. Обратите внимание , что invопределяется как ^:_1, то есть, uприменяется -1 раз.
  • x * yэто продукт из xи y, таким образом , x 10&#.inv@* yдает представление основанию 10 из продукта xи y.
  • x # yкопирует n-й элемент yтак же часто, как n-й элемент x; when x- вектор логических значений, xвыбирает, какие элементы yвзять. Например, 1 0 1 0 # 1 2 3 4урожайность 1 3.
  • * yдает Signum из y.
  • x u~ yявляется рефлексивный из u, то есть такой же , какy u x .
  • Таким образом, y #~ * yдает вектор всех элементов, yкоторые являются положительными. В молчаливом обозначении это может быть написано с крючком как (#~ *).
  • {: yдает последний элемент в y.
  • Собранные вместе, мы получаем молчаливую фразу ([:{:@(#~*)10&#.inv@*).
  • u/ yэто сокращение от y, то есть, двоичного глагол uвставляется между элементами y. Например, +/1 2 3 4это как 1 + 2 + 3 + 4и дает 10.
  • Таким образом, фраза ([:{:@(#~*)10&#.inv@*)/ yдает последнюю цифру произведения пунктов y.
  • ARGV в штучной упаковке вектор аргументов командной строки.
  • ".>{:ARGV последний аргумент распакован и интерпретируется как число.
  • i. yвычисляет натуральные числа от 0доy - 1 .
  • Таким образом, 1+i. yдает натуральные числа от 1до y. Я мог бы также использовать >: приращение здесь, но1+ это более понятно при той же стоимости символов.
  • Вся программа просто применяет 1+i.".>{:ARGV(вектор 1к числу в последнем аргументе командной строки) к глаголу ([:{:@(#~*)10&#.inv@*)/и печатает результат с echo.
FUZxxl
источник
1

R , 63 55 51 46 байт

Вычисляет факториал, извлекает последнюю ненулевую цифру. Спасибо Джузеппе за предоставление базовой структуры.

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

Попробуйте онлайн!

В качестве альтернативы мой старый 51-байтовый ответ:

Вычисляет факториал, преобразует в символ, удаляет все 0s, а затем принимает последний символ. Сохранено 2 байта благодаря Джузеппе.

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

Попробуйте онлайн!

rturnbull
источник
1
gamma(x+1) короче чем factorial(x)
Джузеппе
без преобразования строк лучшее, что мне удалось получить, - (y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]54 байта.
Джузеппе
@Giuseppe Мы можем заменить nchar(x)с 1e5для раствора 46 байт! Хорошо идет.
rturnbull
1

> <> , 25 байт

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

Попробуйте онлайн!

Ручки 0! правильно также. Значение передается через -vфлаг.

Джо Кинг
источник
Тестовый пример 1000не дает никакого вывода на TIO - что не так?
Тоби Спейт
1

Perl 6 ,  26  35 байт

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

Попытайся


Как полная программа:

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

Попытайся

Expanded:

{
  [*]( 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)
  /
}
Брэд Гилберт b2gills
источник
1

C (gcc) , 72 байта (функция)

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

Попробуйте онлайн!

C (gcc) , 101 99 байт (вся программа)

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

Попробуйте онлайн!

Этот вопрос просто стесняется 8 лет, поэтому «разумная машина» - не то же самое, что было тогда, но я получаю время ~ 0,01 секунды на моем компьютере при выполнении всех тестовых случаев вместе, так что, если скорость компьютеров не увеличилась в 1000 раз за последнее десятилетие все должно быть хорошо.

gastropner
источник
Закон Мура все еще (своего рода) остается в силе, поэтому он должен быть примерно в 16 раз быстрее
только для ASCII
Кроме того, функция в порядке
только ASCII
0

Атташе , 26 байт

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

Попробуйте онлайн!

объяснение

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

Это композиция из 4 функций:

  • `! - это функциональная версия факториального оператора
  • Digits - это получает цифры факториала
  • \&:(All@V)- Это функция выбора. Он работает путем левого соединения ( &:) функции All@Vк \, что выбрать. В свою очередь, All@Vэто короткий способ проверки, если число не равно 0. Он работает путем приведения своего ввода к вектору0 -> [0] затем запрашивая, являются ли все эти члены истинными (то есть, не 0). Это дает цифры номера без 0s.
  • Last - это просто получает последний член этого массива.
Конор О'Брайен
источник
Это кажется невероятно медленным - время ожидания TIO (1 минута) в тестовом наборе 100000 - как вы получили результат 1000000 за 10 секунд?
Тоби Спейт
@TobySpeight Когда я ответил на этот вызов, этого конкретного требования не было (проверьте историю изменений).
Конор О'Брайен
Ах, я должен был посмотреть на историю! Вы все же проверили все тестовые случаи в вопросе?
Тоби Спейт
Похоже, что в тот период, когда ограничение по времени было снято с вопроса, было много шуток - это, к сожалению, действительно.
Тоби Спейт
@TobySpeight Да, я сделал. Это прискорбно, и я не уверен в политике в этом отношении.
Конор О'Брайен
0

APL (Dyalog Unicode) , 18 15 байт

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

Попробуйте онлайн!

Функция молчаливого префикса. Возвращает правильную цифру для одного контрольного примера или строку цифр для нескольких контрольных примеров.

Спасибо @ Adám и @ErikTheOutgolfer за 3 байта каждый.

Как?

{⊢/⍵/⍨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.
Ж. Салле
источник
0

APL NARS, 28 байтов, 14 символов

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

Я не знаю, почему, но это пройти тест:

  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
источник
0

AWK , 47 57 байт

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

Попробуйте онлайн!

Исходное решение не очень хорошо обрабатывало «большие» входные значения. Можно добавить, -Mчтобы заставить его работать, но это также требует гораздо больше времени обработки.

Роберт Бенсон
источник
Да, @TobySpeight, infне %очень хорошо. :(
Роберт Бенсон
Ах ... глядя на версию вопроса, на который я ответил, большие цифры не требовались.
Роберт Бенсон
-2

Japt , 6 байт

Придумал несколько разных 6-байтовых символов, но этот мне понравился больше всего. Я уверен, что должен быть способ сделать это в 5, хотя.

Êsw ìv

Попытайся


объяснение

Êвычисляет факториал входных данных, sпреобразует его в строку и обратно в целое число после того, wкак перевернул его, ìпреобразует результат в массив цифр иv возвращает первый элемент.


альтернативы

Êì w æ
ÊìÈf Ì
Êì f o
Êsw sg
Êìf ìo
Êìf ìÌ
мохнатый
источник
Сколько времени это займет, чтобы выполнить все контрольные примеры?
Тоби Спейт
@TobySpeight; это очень легко проверить, перейдя по ссылке, чтобы попробовать это. Обратите внимание, что последние 4 контрольных примера не пройдут, так как их факториалы больше, чем максимальное целое число JavaScript.
лохматый
Значит, это не решит проблему? В вопросе говорится, что он должен быть успешным в течение 1 ≤ N ≤ 1 000 000 . Другие ответы показывают, что вам не нужно сохранять факториал для вычисления ответа.
Тоби Спейт
Я попробовал онлайн-тестирование, но оно истекло в первом тестовом примере, который я попробовал (1000).
Тоби Спейт
-2

Perl 5 , 36 + 10 ( -p -Mbigint) = 46 байт

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

Попробуйте онлайн!

Xcali
источник
Версия TIO не проходит первые два теста, которые я пробовал: 1000000 ⇒ f(должно быть 4 ) и 100 ⇒ 7(должно быть 4 )
Тоби Спейт
Это переполняет размер int. Новая версия работает с использованием bigint. Производительность все еще оставляет желать лучшего, так как это грубый расчет. Это означает, что тайм-аут на TIO для больших чисел.
Xcali