Implement factorial and count trailing zeros
Company: Upstart
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
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.
Quick Answer: 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.
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
Input: 0
Expected Output: 1
Explanation: By definition, 0! = 1.
Input: 1
Expected Output: 1
Explanation: 1! is also 1.
Hints
- Start with result = 1, then multiply by every integer from 2 through n.
- 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
Input: 0
Expected Output: 0
Explanation: 0! = 1, which has no trailing zeros.
Input: 3
Expected Output: 0
Explanation: 3! = 6, so there are no trailing zeros.
Hints
- A trailing zero is created by a factor of 10, which is 2 * 5.
- 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!.