# 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

| Item | Meaning |
|---|---|
| Input | Integer `n` |
| Output | Clumsy factorial of `n` |
| Operators | Cycle through `*`, `/`, `+`, `-` |
| Division | Truncated integer division |

Function shape:

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

## Examples

Example 1:

```python
n = 4
```

```python
4 * 3 / 2 + 1 = 7
```

Answer:

```python
7
```

Example 2:

```python
n = 10
```

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

Answer:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Process each integer from `n` down to `1` |
| Space | `O(n)` | Stack can hold at most `n/4` entries |

## 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

```python
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`:

```python
stack = [n]
```

For each descending number, apply the current operator:

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

`*` and `/` modify the top of the stack:

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

`+` and `-` push new entries:

```python
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:

```python
return sum(stack)
```

## Testing

```python
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()
```

| Test | Expected | Why |
|---|---:|---|
| `4` | `7` | `4*3/2+1 = 7` |
| `10` | `12` | Full example |
| `1` | `1` | Single number |
| `2` | `2` | `2*1 = 2` |
| `3` | `6` | `3*2/1 = 6` |