How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Upstart.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Upstart during technical interviews.

Implement factorial and count trailing zeros

Quick Overview

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.

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.

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 result

Time complexity: O(n) multiplication steps. Space complexity: O(1) auxiliary space, excluding the size of the output integer.

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.

Input: 5

Expected Output: 1

Explanation: 5! = 120, which ends with one zero.

Input: 25

Expected Output: 6

Explanation: Count factors of 5: floor(25/5) = 5 and floor(25/25) = 1, so total = 6.

Input: 100

Expected Output: 24

Explanation: floor(100/5) + floor(100/25) = 20 + 4 = 24.

Solution

def solution(n):
    count = 0
    while n > 0:
        n //= 5
        count += n
    return count

Time complexity: O(log_5 n). Space complexity: O(1).

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!.

Quick Overview