0637MediumMath

Zeros At The End Of The Run Figure

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

At the close of a production run the log posts one figure: the shift numbers 1, 2, up to n all multiplied together. A run of no shifts posts the figure 1.

Write the posted figure in decimal. Return how many zeros stand to the right of its last non-zero digit. Aim for a running time that grows only with the logarithm of n, since for n near the upper bound the figure itself runs to tens of thousands of digits.

Examples

Example 1

Input: n = 24
Output: 4

The figure posted for 24 shifts is 620448401733239439360000, which ends in four zeros before its last non-zero digit 6.

Example 2

Input: n = 124
Output: 28

The figure for 124 shifts is a 208-digit number ending with 28 zeros, so 28 is returned.

Example 3

Input: n = 1249
Output: 308

The figure for 1249 shifts ends with 308 zeros.

Constraints

0 <= n <= 10^4

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def trailing_zeroes(n: int) -> int:

Java

public int trailingZeroes(int n)

The intended approach

Time O(log n) — the divisor is multiplied by five each step.Space O(1).

A zero at the end of the figure is produced by a pair of the factors two and five, and the run always supplies more twos than fives, so the count of fives decides the answer. The shift numbers divisible by five are n // 5 of them, those divisible by twenty-five carry an extra five each, and so on. Adding n // 5, n // 25, n // 125 and onward until the divisor exceeds n gives the total, in a number of steps that grows only logarithmically.

Pythonentry point: trailing_zeroes

def trailing_zeroes(n):
    # O(log n) time, O(1) space: add up how many of the shift numbers carry one
    # factor of five, then how many carry a second, and so on, by dividing n by
    # 5, then 25, then 125, until the divisor passes n. The posted figure itself
    # is never formed.
    total = 0
    step = 5
    while step <= n:
        total += n // step
        step *= 5
    return total

The obvious version

Multiply the shift numbers together into one exact integer, then strip trailing zeros one at a time by dividing by ten while the remainder is zero, counting how many came off.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_trailing_zeroes(n):
    prod = 1
    for i in range(2, n + 1):
        prod *= i
    count = 0
    while prod % 10 == 0:
        prod //= 10
        count += 1
    return count

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in