Implement factorial and count trailing zeros
Company: Upstart
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
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
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.
Input: 5
Expected Output: 120
Explanation: 5! = 1 * 2 * 3 * 4 * 5 = 120.
Input: 10
Expected Output: 3628800
Explanation: 10! = 3628800.
Input: 20
Expected Output: 2432902008176640000
Explanation: This checks that the solution handles larger integer results correctly.
Solution
def solution(n):
result = 1
for i in range(2, n + 1):
result *= i
return resultTime complexity: O(n) multiplication steps. Space complexity: O(1) auxiliary space, excluding the size of the output integer.