DSA sheet / Introductory
Trailing Zeros
The problem in brief
Given n up to 10^9, print the number of zeros at the end of the decimal representation of n! (n factorial).
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1618.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
n! has millions of digits for large n, so you can never write it down. What creates a trailing zero in a product of integers?
-
A trailing zero means a factor of 10 = 2 * 5. Between the factors 2 and 5 in n!, which one is scarcer?
-
Count the multiples of 5 up to n. Then notice that 25 contributes two fives, 125 contributes three, and so on. How do you avoid undercounting them?
-
The count is a sum of floor divisions. Which loop bound stops the sum, and can the running power of 5 overflow?
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
Refuse to compute the number. Trailing zeros are a statement about divisibility, so translate the question into prime factorisation: the number of trailing zeros of N is the exponent of 10 in N, which is min(exponent of 2, exponent of 5). In a factorial, even numbers are far more common than multiples of 5, so twos are never the bottleneck; the answer is just the exponent of 5 in n!.
Then count fives smartly: each multiple of 5 up to n gives one five, each multiple of 25 gives one more, each multiple of 125 one more, and so on. That is floor(n/5) + floor(n/25) + floor(n/125) + … (Legendre’s formula). Verify it against real factorials for n up to a few hundred; the transferable habit is to cross-check a formula with a tiny brute force.
Intuition
Imagine writing 1 * 2 * 3 * … * n and circling every 5 you see hidden inside the numbers. 5, 10, 15, 20 have one each; 25 hides two; 125 hides three. You are counting the circled fives, and every ten needs one five and one (plentiful) two.
Approach
- Set count = 0 and p = 5.
- While p <= n: add n / p (integer division) to count, then multiply p by 5.
- Print count.
Pitfall: p goes up to about 5n, which is 5 * 10^9 and overflows a 32-bit int, so use 64-bit for p. Do not try to compute n! even modulo something; the loop needs only about 13 iterations.
Complexity
O(log_5 n) time, O(1) memory.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
long long count = 0;
for (long long p = 5; p <= n; p *= 5) count += n / p;
cout << count << "\n";
return 0;
}import sys
def main():
n = int(sys.stdin.readline())
count = 0
p = 5
while p <= n:
count += n // p
p *= 5
print(count)
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
long n = Long.parseLong(in.readLine().trim());
long count = 0;
for (long p = 5; p <= n; p *= 5) count += n / p;
System.out.println(count);
}
}const n = Number(require('fs').readFileSync(0, 'utf8').trim());
let count = 0;
for (let p = 5; p <= n; p *= 5) count += Math.floor(n / p);
console.log(count);Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).