Напишите программу или функцию, которая находит число нулей в конце n!
в базе 10, где n
это число ввода (в любом желаемом формате).
Можно предположить, что n
это положительное целое число, то n!
есть это также целое число. Там нет нулей после десятичной точки в n!
. Также можно предположить, что ваш язык программирования может обрабатывать значения n
и n!
.
Контрольные примеры
1
==> 0
5
==> 1
100
==> 24
666
==> 165
2016
==> 502
1234567891011121314151617181920
==> 308641972752780328537904295461
Это код гольф. Стандартные правила применяются. Самый короткий код в байтах побеждает.
Материалы
Чтобы убедиться, что ваш ответ обнаружен, начните его с заголовка, используя следующий шаблон уценки:
# Language Name, N bytes
где N
размер вашего представления. Если вы улучшите свой счет, вы можете сохранить старые результаты в заголовке, вычеркнув их. Например:
# Ruby, <s>104</s> <s>101</s> 96 bytes
Если вы хотите включить в заголовок несколько чисел (например, потому что ваш результат равен сумме двух файлов или вы хотите перечислить штрафы за флаг интерпретатора отдельно), убедитесь, что фактический результат является последним числом в заголовке:
# Perl, 43 + 2 (-p flag) = 45 bytes
Вы также можете сделать название языка ссылкой, которая затем будет отображаться во фрагменте списка лидеров:
# [><>](http://esolangs.org/wiki/Fish), 121 bytes
Leaderboard
Вот фрагмент стека, который генерирует как регулярную таблицу лидеров, так и обзор победителей по языкам.
/* Configuration */
var QUESTION_ID = 79762; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 43444; // This should be the user ID of the challenge author.
/* App */
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;
function answersUrl(index) {
return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function commentUrl(index, answers) {
return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}
function getAnswers() {
jQuery.ajax({
url: answersUrl(answer_page++),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
answers.push.apply(answers, data.items);
answers_hash = [];
answer_ids = [];
data.items.forEach(function(a) {
a.comments = [];
var id = +a.share_link.match(/\d+/);
answer_ids.push(id);
answers_hash[id] = a;
});
if (!data.has_more) more_answers = false;
comment_page = 1;
getComments();
}
});
}
function getComments() {
jQuery.ajax({
url: commentUrl(comment_page++, answer_ids),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
answers_hash[c.post_id].comments.push(c);
});
if (data.has_more) getComments();
else if (more_answers) getAnswers();
else process();
}
});
}
getAnswers();
var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;
var OVERRIDE_REG = /^Override\s*header:\s*/i;
function getAuthorName(a) {
return a.owner.display_name;
}
function process() {
var valid = [];
answers.forEach(function(a) {
var body = a.body;
a.comments.forEach(function(c) {
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});
var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
link: a.share_link,
});
});
valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});
var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;
var answer = jQuery("#answer-template").html();
answer = answer.replace("{{PLACE}}", lastPlace + ".")
.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)
.replace("{{LINK}}", a.link);
answer = jQuery(answer);
jQuery("#answers").append(answer);
var lang = a.language;
if (/<a/.test(lang)) lang = jQuery(lang).text();
languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
});
var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);
langs.sort(function (a, b) {
if (a.lang > b.lang) return 1;
if (a.lang < b.lang) return -1;
return 0;
});
for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
.replace("{{LINK}}", lang.link);
language = jQuery(language);
jQuery("#languages").append(language);
}
}
body { text-align: left !important}
#answer-list {
padding: 10px;
width: 290px;
float: left;
}
#language-list {
padding: 10px;
width: 290px;
float: left;
}
table thead {
font-weight: bold;
}
table td {
padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
<h2>Leaderboard</h2>
<table class="answer-list">
<thead>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
</thead>
<tbody id="answers">
</tbody>
</table>
</div>
<div id="language-list">
<h2>Winners by Language</h2>
<table class="language-list">
<thead>
<tr><td>Language</td><td>User</td><td>Score</td></tr>
</thead>
<tbody id="languages">
</tbody>
</table>
</div>
<table style="display: none">
<tbody id="answer-template">
<tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
<tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
n
быть строка ввода?n!
что он соответствует вашему целочисленному типу! Ну, может быть, в другой раз.Ответы:
Python 2, 27 байт
Концовка нули ограничены факторами 5. Число кратных ,
5
что не более чемn
вn/5
(с пол деления), но это не считается повторяющиеся факторы в упаковке25, 125, ...
. Чтобы получить их, разделитеn
на 5 и рекурсивно.источник
Желе , 5 байт
Использует контрпродуктивный подход: найти факториал, а затем снова разложить его на множители, проверяя показатель степени 5 в первичной факторизации.
Попробуйте онлайн!
источник
Морнингтон Кресент,
1949 г.1909 байт-40 байт благодаря NieDzejkob
источник
Mornington Crescent
вызов, было бы здорово. :)Pyth, 6 байт
Попробуй это здесь.
Альтернатива 7 байт :
Суммарное уменьшение
.u/N5
многократно делит на пол5
до тех пор, пока не получит повторение, что в этом случае происходит после того, как оно достигнет 0.Первый элемент затем удаляется (
t
), а остальные суммируются (s
).источник
На самом деле, 10 байтов
Попробуйте онлайн!
Обратите внимание, что последний тестовый пример не выполняется при запуске Seriously на CPython, потому что
math.factorial
используется расширение C (которое ограничено 64-разрядными целыми числами). Хотя серьезно работает на PyPy работает нормально.Объяснение:
источник
Haskell, 26 байтов
Этаж делит ввод на
5
, затем добавляет результат к вызываемой функции. Выражение(+)=<<f
принимает входx
и выходx+(f x)
.Сокращенный от:
Нерекурсивное выражение дало 28 байтов:
источник
i
счетчик от1..n
?log_5(n)
делам, остальные дают 0.MATL , 9 байт
Попробуйте онлайн!
Это работает для очень больших чисел, поскольку позволяет избежать вычисления факториала.
Как и другие ответы, это использует тот факт, что число раз, которое
2
появляется, поскольку делитель факториала больше или равно числу раз, которое5
появляется.источник
05AB1E, 5 байтов
Было бы 4 байта, если бы мы могли гарантировать n> 4
Код:
Объяснение:
Альтернативное, намного более быстрое, 6-байтовое решение: вдохновлено ответом Луиса Мендо на MATL
Объяснение:
Редактировать: удаленные решения, использующие ¢ (количество), поскольку все простые числа, содержащие 5, будут считаться как 5, например, 53.
Редактировать 2: добавлено более эффективное решение для более высокого ввода в качестве сравнения.
источник
5¢
,5Q
чтобы работать. Хороший ответ, хотя! :)Ó
идет медленноÎ!Ó2é
. Ошибка была исправлена вчера .Î!Ó7è
это 8 байтов, а "6-байтовое" решение составляет 10 байтовMatlab
(59) (54)(39)Эй, черт возьми !!!! мы слышали, вы как математика ....
Это основано на моем созданном ответе в обзоре кода .
Кроме того, что упомянуто в моем ответе в обзоре кода, формула для числа нулей в факториале (n) равна сумме (n / (5 ^ k)), где k изменяется от 1 до log_5 (n)
Единственная тривиальная причина, по которой он не может стать игроком в гольф, заключается в том, что он
log5
не доступен в matlab как встроенный, поэтому я заменил log (5) на 1.6, не имеет значения, потому что он в любом случае будет зависать.Попробуй
источник
Mathematica, 20 байтов
IntegerExponent
считает нули. Для забавы, вот версия, которая не рассчитывает факториал:источник
Array
экономит байт на втором решении.C, 28 байтов
объяснение
Число конечных нулей равно числу пятерок, составляющих факториал. Из всех
1..n
, одна пятая из них внести свой вклад в пять, так что мы начнем сn/5
. Из нихn/5
пятая - это кратные 25, поэтому добавьте еще пять и так далее. Мы заканчиваем темf(n) = n/5 + n/25 + n/125 + ...
, что естьf(n) = n/5 + f(n/5)
. Нам нужно прекратить рекурсию, когдаn
достигнет нуля; Кроме того, мы используем точку последовательности,?:
чтобы разделитьn
перед сложением.В качестве бонуса, этот код намного быстрее, чем тот, который посещает каждый
1..n
(и намного, намного быстрее, чем вычисление факториала).Тестовая программа
Тестовый вывод
источник
JavaScript ES6, 20 байт
Та же тактика, что и в ответе xnor, но короче.
источник
Юлия,
343130 байтThis is an anonymous function that accepts any signed integer type and returns an integer. To call it, assign it to a variable. The larger test cases require passing
n
as a larger type, such as aBigInt
.We compute the factorial of
n
(manually usingprod
is shorter than the built-infactorial
), get an array of itsdigits
in reverse order,find
the indices of the nonzero elements, get the first such index, and subtract 1.Try it online! (includes all but the last test case because the last takes too long)
Saved a byte thanks to Dennis!
источник
C, 36
Same method as @xnor's answer of counting 5s, but just using a simple for loop instead of recursion.
Ideone.
источник
Retina, 33 bytes
Takes input in unary.
Returns output in unary.
(Note the trailing linefeed.)
Try it online!
How it works:
The first stage:
Slightly ungolfed:
What it does:
11111
that can be matched.5
.(?=1)
assures that the number is positive.+`
means repeat until idempotent.If the input is 100 (in unary), then the text is now:
Second stage:
Just removes all semi-colons.
источник
Ruby, 22 bytes
One of the few times where the Ruby
0
being truthy is a problem for byte count.источник
0
truthy?nil
andfalse
are falsey, and nothing else is. There are a lot of cases where helps out in golf, since having0
be truthy means the index and regex index functions in Ruby returnnil
if there is no match instead of-1
, and some where it is a problem, like empty strings still being truthy.Perl 6, 23 bytes
I could get it shorter if
^...
was added to Perl 6{sum $_,*div 5^...0}
.It should be more memory efficient for larger numbers if you added a
lazy
modifier betweensum
and the sequence generator.Explanation:
Test:
( That last line is slightly misleading, as MoarVM has to start, load the Perl 6 compiler and runtime, compile the code, and run it. So it actually takes about a second and a half in total.
That is still significantly faster than it was to check the result of the last test with WolframAlpha.com )
источник
Mathcad, [tbd] bytes
Mathcad is sort of mathematical "whiteboard" that allows 2D entry of expressions, text and plots. It uses mathematical symbols for many operations, such as summation, differentiation and integration. Programming operators are special symbols, usually entered as single keyboard combinations of control and/or shift on a standard key.
What you see above is exactly how the Mathcad worksheet looks as it is typed in and as Mathcad evaluates it. For example, changing n from 2016 to any other value will cause Mathcad to update the result from 502 to whatever the new value is.
http://www.ptc.com/engineering-math-software/mathcad/free-download
Mathcad's byte equivalence scoring method is yet to be determined. Taking a symbol equivalence, the solution takes about 24 "bytes" (the while operator can only be entered using the "ctl-]" key combination (or from a toolbar)). Agawa001's Matlab method takes about 37 bytes when translated into Mathcad (the summation operator is entered by ctl-shft-$).
источник
dc, 12 bytes
This defines a function
f
which consumes its input from top of stack, and leaves its output at top of stack. See my C answer for the mathematical basis. We repeatedly divide by 5, accumulating the values on the stack, then add all the results:Test program
Test output
источник
Jolf, 13 bytes
Defines a recursive function which is called on the input. Try it here!
источник
J,
281716 bytesPretty much the same as the non-recursive technique from xnor's answer.
Here's an older version I have kept here because I personally like it more, clocking in at 28 bytes:
Whilst not needed, I have included
x:
in the test cases for extended precision.The last number doesn't work with this function.
Explanation
This works by calculating
n!
, converting it to a string, and checking each member for equality with'0'
. Forn = 15
, this process would be:Now, we use
;._1
to split the list on its first element (zero), boxing each split result, yielding a box filled with aces (a:
) or runs of1
s, like so:We simple obtain the last member (
{:
), unbox it (>
), and perform a summation over it+/
, yielding the number of zeroes.Here is the more readable version:
источник
>:@i.
can be written1+i.
to save a byte.[:#.~'0'=":@!
for 13 bytes by changing the method of counting the trailing 1s.Python 3, 52 bytes
источник
Pyke, 5 bytes
Try it here!
источник
RETURN, 17 bytes
Try it here.
Recursive operator lambda. Usage:
Explanation
источник
Perl,
2422 + 1 (-p
flag) = 23 bytesUsing:
Full program:
источник
Java, 38 bytes
Full program, with ungolfed method:
источник
J, 7 bytes
Monadic function, taking argument on the right.
If
x
is positive,x q: y
returns the exponents in a prime factorization ofy
, for only the firstx
primes. The3
-rd prime is 5 and{:
takes the tail of a list.Note that you have to input integers with an
x
at the end, or else J will treat them as floats.Try it yourself at tryj.tk, though be warned that this online interpreter will complain if you try anything larger than 1343.
If you want something that doesn't compute n! and hence doesn't require it fit in an integer, use the recursive solution
<.@%&5(+$:@)^:*
. (tryj.tk is still whiny on large inputs.)источник
Ruby,
70615149 bytesVersion 3 with thanks to Kenny Lau and daniero
Edit: Turns out you can save two bytes by mapping
to_i
before youreduce
. Weird :PThis function subtracts the sum of
n
's base 5 digits fromn
and then divides that result by 4. This is related to the sum of the geometric series1+5+25+..+5**n = (5**n+1)/4
.As an example (again, with thanks to Kenny Lau), consider
358
(2413
in base 5) minus its base 5 digits.Divide
348
by4
and you getf(358) = 87
.Version 2 with thanks to Kenny Lau
This function calculates
n!
then subtracts thesize
ofn!
from thesize
of(n!).reverse.to_i.to_s
, which removes all the zeroes, thus, returning thesize
of the zeroes themselves.Version 1
This a variation of the "How many
5
s are there in the prime factorization ofn!
?" trick that uses Ruby's simple base conversion builtins.The golfing is a bit of a pain though, with converting from
Integer
toString
toArray
, grabbing part of theArray
and converting that toString
toInteger
again for thereduce
. Any golfing suggestions are welcome.источник
to_i
before reducing:->n{(n-n.to_s(5).chars.map(&:to_i).reduce(:+))/4}
(saves two bytes)Julia,
2119 bytesUses the recursive formula from xnor's answer.
Try it online!
источник
Dyalog APL, 9 bytes
⎕
prompt for number!
factorialize⍕
stringify'0'=
check equality to character zero⊥⍨
count trailing trues**Literally it is a mixed-base to base-10 conversion, using the boolean list as both number and base:
⊥⍨0 1 0 1 1
is the same as0 1 0 1 1⊥⍨0 1 0 1 1
which is0×(0×1×0×1×1) 1×(1×0×1×1) 0×(0×1×1) 1×(1×1) + 1×(1)
which again is two (the number of trailing 1s).источник