LeetCode 1006: Clumsy Factorial

Problem Restatement

The clumsy factorial of a positive integer n is defined as follows:

Start from n and apply operators *, /, +, - in a fixed cyclic order, descending through integers.

For example, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1.

Division is integer division truncated toward zero.

We need to return the clumsy factorial of n.

The official constraints state that 1 <= n <= 10000.

Input and Output

Function shape:

def clumsy(n: int) -> int:
    ...

Examples

Example 1:

n = 4

4 * 3 / 2 + 1 = 7

Answer:

7

Example 2:

n = 10

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

Answer:

12

Key Insight

Operator precedence matters: * and / bind tighter than + and -.

We can use a stack to handle this. Push numbers and compute * and / immediately. Then push the result. For +, push the next number. For -, push the negation of the next group.

This ensures that * and / are evaluated before + and -.

Algorithm

1. Use a stack. Push n.
2. Track the current operator (start with * for the second number).
3. For each subsequent number i from n-1 down to 1:
   • Apply the current operator to stack[-1] and i, or push the new number.
   • For *: stack[-1] *= i
   • For /: stack[-1] = int(stack[-1] / i) (truncate toward zero)
   • For +: stack.append(i)
   • For -: stack.append(-i)
   • Cycle to the next operator.
4. Return sum(stack).

Correctness

By applying * and / directly to the top of the stack, we respect their higher precedence.

By pushing the result of + (positive) and - (negative) as separate entries, we correctly handle their lower precedence.

The final sum of the stack gives the correct result with all precedences respected.

Edge Cases

• The stack should store exactly the unresolved items needed by the invariant.
• Process equal values deliberately; many monotonic-stack problems differ only in < versus <=.
• Flush or inspect the remaining stack after the scan if unresolved items still contribute to the answer.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

import math

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

        for i in range(n - 1, 0, -1):
            op = ops[op_idx % 4]
            op_idx += 1

            if op == '*':
                stack[-1] *= i
            elif op == '/':
                stack[-1] = math.trunc(stack[-1] / i)
            elif op == '+':
                stack.append(i)
            else:
                stack.append(-i)

        return sum(stack)

Code Explanation

Initialize the stack with n:

stack = [n]

For each descending number, apply the current operator:

op = ops[op_idx % 4]
op_idx += 1

* and / modify the top of the stack:

if op == '*':
    stack[-1] *= i
elif op == '/':
    stack[-1] = math.trunc(stack[-1] / i)

+ and - push new entries:

elif op == '+':
    stack.append(i)
else:
    stack.append(-i)

We use math.trunc to ensure truncation toward zero for negative divisions.

Return the total sum:

return sum(stack)

Testing

def run_tests():
    s = Solution()

    assert s.clumsy(4) == 7
    assert s.clumsy(10) == 12
    assert s.clumsy(1) == 1
    assert s.clumsy(2) == 2
    assert s.clumsy(3) == 6

    print("all tests passed")

run_tests()