cswork / libraryOpen practice workspace

Coding questions · Upstart

Implement factorial and count trailing zeros

This question evaluates understanding of factorial computation and algorithmic techniques, including iterative versus recursive approaches, handling large integers and recursion constraints, and efficient counting of trailing zeros via number-theoretic reasoning.

Answer the following coding questions in Python.

1) Implement factorial

Implement a function factorial(n) that returns $n!$ for a non-negative integer n.

  • Describe at least two different implementation approaches (e.g., iterative, recursive), and discuss constraints (e.g., recursion depth, large integers).

2) Count trailing zeros of a factorial

Given an integer n, compute the number of trailing zeros in the decimal representation of $n!$ (i.e., how many zeros at the end).

  • Your solution should be efficient for large n (do not compute $n!$ explicitly).
  • Specify time complexity.

Part 1: Implement Factorial

Given a non-negative integer n, return n!, the product of all positive integers from 1 to n. For example, 5! = 120. You may solve this iteratively or recursively, but be careful: recursive solutions in Python can hit recursion-depth limits for large n. Do not use math.factorial.

Constraints

  • 0 <= n <= 2000
  • n is an integer
  • Do not use math.factorial or other built-in factorial helpers

Examples

Example 1

Input: 0
Output: 1

Explanation: By definition, 0! = 1.

Example 2

Input: 1
Output: 1

Explanation: 1! is also 1.

Hints

  1. Start with result = 1, then multiply by every integer from 2 through n.
  2. Remember the edge cases: 0! = 1 and 1! = 1. Iteration avoids recursion stack limits.

Part 2: Count Trailing Zeros of a Factorial

Given a non-negative integer n, return the number of trailing zeros in the decimal representation of n!. Your algorithm must be efficient for large n, so do not compute n! explicitly.

Constraints

  • 0 <= n <= 10^18
  • n is an integer
  • Do not compute n! directly

Examples

Example 1

Input: 0
Output: 0

Explanation: 0! = 1, which has no trailing zeros.

Example 2

Input: 3
Output: 0

Explanation: 3! = 6, so there are no trailing zeros.

Hints

  1. A trailing zero is created by a factor of 10, which is 2 * 5.
  2. In n!, factors of 2 are more common than factors of 5, so count how many times 5 appears in the prime factorization of n!.