Clumsy Factorial: Stack-Based Expression Evaluation

Clumsy Factorial is LeetCode 1006, rated Medium. The normal factorial of N multiplies all integers from N down to 1: N * (N-1) * ... * 1. The "clumsy" version replaces the multiplication signs with a rotating cycle of four operations: *, /, +, -, repeating in that order.

So for N = 10, the clumsy factorial is:

10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

Division is integer division that truncates toward zero. You need to respect standard operator precedence: * and / bind tighter than + and -. That means you cannot just evaluate left to right. You need a way to handle groups.

Why this problem matters

This problem is really about evaluating an expression with mixed operator precedence. The same pattern shows up in calculator problems (Basic Calculator II), compiler tokenizers, and any situation where you parse a mathematical expression and need to handle *// before +/-. Once you learn the stack-based approach here, you can apply it to a whole family of expression evaluation problems.

The key insight

The trick is to recognize that * and / are high-precedence operators that should be applied immediately, while + and - are low-precedence operators that define boundaries between terms.

You can use a stack to manage this. Walk through the numbers from N down to 1, cycling through the four operations. For each number:

• If the current operation is *, pop the top of the stack, multiply, and push the result back.
• If the current operation is /, pop the top, divide (truncating toward zero), and push the result back.
• If the current operation is +, just push the number onto the stack.
• If the current operation is -, push the negated number onto the stack.

At the end, sum all values on the stack. The negated values naturally subtract themselves during the sum.

This works because * and / always operate on the most recent term (the top of stack), while + and - start a new term. The stack collects all the terms, and the final summation combines them.

The solution

def clumsy(n: int) -> int:
    ops = ["*", "/", "+", "-"]
    stack = [n]
    op_idx = 0

    for i in range(n - 1, 0, -1):
        op = ops[op_idx % 4]
        if op == "*":
            stack.append(stack.pop() * i)
        elif op == "/":
            stack.append(int(stack.pop() / i))
        elif op == "+":
            stack.append(i)
        else:
            stack.append(-i)
        op_idx += 1

    return sum(stack)

The loop counts down from n - 1 to 1, which gives us the N-1 numbers that follow the first number. We track which operation to use with op_idx % 4, cycling through the four operations in order.

For * and /, we pop the top of the stack, apply the operation, and push the result. This handles the higher precedence by collapsing those operations immediately. For +, we push the number as-is. For -, we push the negated value so that summing the stack at the end gives the correct subtraction.

The division uses int(stack.pop() / i) rather than // to get truncation toward zero. Python's // floors toward negative infinity, which gives wrong results for negative numbers. For example, -30 // 4 is -8 in Python, but the correct truncation toward zero is -7.

Visual walkthrough

Notice how the stack never grows very large. Each * and / collapses the top element, so the stack only grows when + or - push new terms. For clumsy(10), the stack holds at most 5 values before the final summation.

Complexity analysis

Time: O(n). We iterate through all numbers from N down to 1 exactly once. Each iteration does a constant amount of work: one stack operation and possibly one arithmetic operation.

Space: O(n). In the worst case, the stack stores about n/4 terms (one for each + or - operation, plus the initial group). This simplifies to O(n). You could optimize to O(1) space by keeping a running total instead of a stack, but the stack version is clearer and the space difference rarely matters in practice.

The building blocks

1. Stack-based expression evaluation

The core pattern here is using a stack to handle operator precedence. High-precedence operators (* and /) modify the top of the stack immediately. Low-precedence operators (+ and -) push new values that get combined later. This is the same idea behind Basic Calculator II and many expression parsing problems. The stack acts as a buffer that lets you defer the low-precedence additions and subtractions until all the high-precedence work is done.

2. Cycling through operators

Using modular arithmetic to rotate through a fixed sequence of operations is a small but reusable pattern. You define your sequence (here [*, /, +, -]) and index into it with i % len. This avoids messy if-else chains based on position and makes the code easy to adjust if the operation order changes.

Edge cases

• N = 1: just return 1. There are no operations to apply.
• N = 2: 2 * 1 = 2. Only the first operation fires.
• N = 3: 3 * 2 / 1 = 6. Two operations, both high precedence.
• N = 4: 4 * 3 / 2 + 1 = 7. All four operations appear once.

These small cases are worth checking because the loop boundaries and the cycling logic can easily be off by one.

From understanding to recall

The clumsy factorial solution is short, maybe 12 lines. But the details matter: which direction does integer division truncate? Do you push i or -i for subtraction? Does the operation index start at 0 or 1?

These are the kinds of details that slip away after a week. You understand the algorithm right now, but reproducing it from scratch under pressure is a different skill. Spaced repetition closes that gap. You write the stack-based evaluator from memory at increasing intervals, and each repetition reinforces the cycle logic, the division truncation, and the push/pop pattern. After a few rounds, the code comes out automatically.

Related posts

• Evaluate Reverse Polish Notation - Stack-based expression evaluation
• Basic Calculator - More complex expression parsing with stacks
• Basic Calculator II - Expression evaluation with operator precedence

CodeBricks breaks the clumsy factorial problem into its reusable building blocks and drills them with spaced repetition. You type the solution from scratch each time, so when LeetCode 1006 or any operator-precedence evaluation problem shows up in an interview, the code flows without hesitation.