# Clumsy Factorial
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/clumsy-factorial)
Canonical: https://scaleengineer.com/dsa/problems/clumsy-factorial
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Stack
---
## Problem
The **factorial** of a positive integer `n` is the product of all positive integers less than or equal to `n`.

* For example, `factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1`.

We make a **clumsy factorial** using the integers in decreasing order by swapping out the multiply operations for a fixed rotation of operations with multiply `'*'`, divide `'/'`, add `'+'`, and subtract `'-'` in this order.

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

However, these operations are still applied using the usual order of operations of arithmetic. We do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.

Additionally, the division that we use is floor division such that `10 * 9 / 8 = 90 / 8 = 11`.

Given an integer `n`, return _the clumsy factorial of_ `n`.

**Example 1:**

**Input:** n = 4
**Output:** 7
**Explanation:** 7 = 4 * 3 / 2 + 1

**Example 2:**

**Input:** n = 10
**Output:** 12
**Explanation:** 12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

**Constraints:**

* `1 <= n <= 104`

# Approaches
## Stack-based Simulation
This approach directly simulates the evaluation of the clumsy factorial expression. Due to the standard order of operations (PEMDAS/BODMAS), where multiplication and division have higher precedence than addition and subtraction, a stack is a natural data structure to use. We can process the numbers from `n` down to 1, performing multiplications and divisions immediately on the top of the stack, while deferring additions and subtractions by pushing new terms onto the stack. The final result is the sum of all numbers left in the stack.
**Time:** O(N), as we iterate through the numbers from `n` to 1 once. The final summation also takes O(N) in the worst case. · **Space:** O(N), as the stack can store up to `n/4 + 1` terms in the worst case, which is proportional to `n`.
**Pros:** Conceptually straightforward and directly models the expression evaluation process.; Easy to implement and debug.
**Cons:** Uses extra space for the stack, which is not optimal compared to other approaches.
### Explanation
We iterate from `n` down to 1, keeping track of the current operation in the cycle `*`, `/`, `+`, `-`. A stack is used to store the intermediate terms that will eventually be summed up. When we encounter a `*` or `/` operation, we apply it to the last term we were calculating, which is conveniently at the top of the stack. We pop the value, perform the operation with the current number, and push the result back. When we encounter a `+` or `-` operation, it signals the end of the previous term and the beginning of a new one. We simply push the current number (or its negation for `-`) onto the stack as a new term. After iterating through all the numbers, the stack contains all the terms of the expression (e.g., for `n=10`, it would hold `[11, 7, -7, 3, -2]`). The final step is to sum up all the values in the stack to get the answer.

For example, with `n=4` (`4 * 3 / 2 + 1`):
1.  Push `4`. Stack: `[4]`
2.  Op is `*`. Pop `4`, push `4 * 3 = 12`. Stack: `[12]`
3.  Op is `/`. Pop `12`, push `12 / 2 = 6`. Stack: `[6]`
4.  Op is `+`. Push `1`. Stack: `[6, 1]`
5.  Sum stack: `6 + 1 = 7`.

```java
import java.util.Stack;

class Solution {
    public int clumsy(int n) {
        if (n <= 2) {
            return n;
        }
        
        Stack<Integer> stack = new Stack<>();
        stack.push(n);
        
        int op = 0; // 0:*, 1:/, 2:+, 3:-
        for (int i = n - 1; i > 0; i--) {
            if (op % 4 == 0) { // *
                stack.push(stack.pop() * i);
            } else if (op % 4 == 1) { // /
                stack.push(stack.pop() / i);
            } else if (op % 4 == 2) { // +
                stack.push(i);
            } else { // -
                stack.push(-i);
            }
            op++;
        }
        
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        
        return result;
    }
}
```
### Algorithm
*   Handle base cases for `n <= 2` by returning `n`.
*   Initialize an empty stack of integers.
*   Push the first number, `n`, onto the stack.
*   Initialize an operation counter, `op_idx = 0`.
*   Loop for `i` from `n-1` down to `1`:
    *   If `op_idx % 4 == 0` (multiplication): Pop from the stack, multiply by `i`, and push the result.
    *   If `op_idx % 4 == 1` (division): Pop from the stack, divide by `i`, and push the result.
    *   If `op_idx % 4 == 2` (addition): Push `i` onto the stack.
    *   If `op_idx % 4 == 3` (subtraction): Push `-i` onto the stack.
    *   Increment `op_idx`.
*   After the loop, calculate the sum of all elements in the stack and return it.

## Iterative Simulation with O(1) Space
This approach improves upon the stack-based method by realizing that we don't need to store all the intermediate terms. Instead of a stack, we can use a few variables to keep track of the overall result and the value of the current term being calculated (the one involving multiplications and divisions).
**Time:** O(N), as we still iterate through the numbers from `n` to 1. · **Space:** O(1), as we only use a few variables to store the state, regardless of `n`.
**Pros:** More efficient than the stack approach due to constant space usage.; Still follows the logic of the calculation directly.
**Cons:** Still requires a full iteration through the numbers, which is slower than a constant-time solution.
### Explanation
The core idea is to maintain a running `result` and the `current_term`. The `result` accumulates the values of completed terms (those separated by `+` or `-`). The `current_term` is built up using `*` and `/` operations. We start by initializing `current_term` with the first number, `n`. We then loop from `n-1` down to 1. For each number `i`, we check the corresponding operation. If the operation is `*` or `/`, we update `current_term` by applying the operation with `i`. If the operation is `+` or `-`, it means the `current_term` we were just building is now complete. We add this `current_term` to the final `result`. Then, we start a new `current_term` with the current number `i` (or `-i` if the operation was subtraction). After the loop finishes, the very last `current_term` has been calculated but not yet added to the `result`. A final addition is needed before returning the total.

For example, with `n=10`:
1.  `result = 0`, `current_term = 10`.
2.  `i=9` (op `*`): `current_term` becomes `10 * 9 = 90`.
3.  `i=8` (op `/`): `current_term` becomes `90 / 8 = 11`.
4.  `i=7` (op `+`): Term `11` is complete. `result += 11` (`result=11`). Start new term: `current_term = 7`.
5.  `i=6` (op `-`): Term `7` is complete. `result += 7` (`result=18`). Start new term: `current_term = -6`.
6.  ...and so on.
7.  After the loop, add the last `current_term` to `result`.

```java
class Solution {
    public int clumsy(int n) {
        if (n <= 2) return n;
        if (n == 3) return 6; // Can be handled by the loop, but this is a small optimization
        
        int result = 0;
        int currentTerm = n;
        int op = 0; // 0:*, 1:/, 2:+, 3:-

        for (int i = n - 1; i > 0; i--) {
            if (op % 4 == 0) { // *
                currentTerm *= i;
            } else if (op % 4 == 1) { // /
                currentTerm /= i;
            } else if (op % 4 == 2) { // +
                result += currentTerm;
                currentTerm = i;
            } else { // -
                result += currentTerm;
                currentTerm = -i;
            }
            op++;
        }
        
        result += currentTerm;
        return result;
    }
}
```
### Algorithm
*   Handle base cases for `n <= 2` by returning `n`.
*   Initialize `result = 0` and `current_term = n`.
*   Initialize an operation counter, `op_idx = 0`.
*   Loop for `i` from `n-1` down to `1`:
    *   If `op_idx % 4 == 0` (multiplication): `current_term *= i`.
    *   If `op_idx % 4 == 1` (division): `current_term /= i`.
    *   If `op_idx % 4 == 2` (addition): Add `current_term` to `result`, then reset `current_term = i`.
    *   If `op_idx % 4 == 3` (subtraction): Add `current_term` to `result`, then reset `current_term = -i`.
    *   Increment `op_idx`.
*   After the loop, add the final `current_term` to `result`.
*   Return `result`.

## Mathematical Pattern Recognition
By analyzing the clumsy factorial expression for larger values of `n`, a surprising mathematical pattern emerges. The expression can be broken down into groups of four numbers, and for `n >= 5`, these groups simplify in a predictable way, leading to a repeating pattern in the final result. This allows us to compute the answer in constant time.
**Time:** O(1), as the calculation involves a few conditional checks and basic arithmetic, independent of the value of `n`. · **Space:** O(1), as no extra space that scales with `n` is required.
**Pros:** Extremely efficient, providing a solution in constant time and space.
**Cons:** Relies on observing a non-obvious mathematical pattern.; The proof of why the pattern holds is not trivial and hard to derive during an interview.
### Explanation
Let's analyze the expression in chunks of four: `... + a - b * c / d ...`. Due to operator precedence, this is `... + a - (b * c / d) ...`. A key observation is that for any integer `k >= 5`, the floor division `k * (k-1) / (k-2)` simplifies to `k+1`. So, if we look at a chunk of the expression like `+ (n-3) - (n-4) * (n-5) / (n-6)`, and if `n-4 >= 5` (i.e., `n >= 9`), the term `(n-4) * (n-5) / (n-6)` simplifies to `(n-4)+1 = n-3`. The expression chunk then becomes `+ (n-3) - (n-3)`, which cancels out to 0. This cancellation of groups of four continues as long as the numbers involved are 5 or greater. This implies that the final result depends only on the first few terms and the last few terms (where the numbers are less than 5). By computing the results for `n=1, 2, 3, 4, 5, 6, 7, 8, ...`, we can observe a clear pattern for `n >= 5`:

*   `n % 4 == 0`: result is `n + 1` (e.g., `clumsy(8) = 9`)
*   `n % 4 == 1`: result is `n + 2` (e.g., `clumsy(5) = 7`, `clumsy(9) = 11`)
*   `n % 4 == 2`: result is `n + 2` (e.g., `clumsy(6) = 8`, `clumsy(10) = 12`)
*   `n % 4 == 3`: result is `n - 1` (e.g., `clumsy(7) = 6`)

We can therefore create a solution that handles `n <= 4` as special cases and then applies this formula for `n > 4`.

```java
class Solution {
    public int clumsy(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        if (n == 3) return 6;
        if (n == 4) return 7;
        
        int rem = n % 4;
        if (rem == 0) {
            return n + 1;
        } else if (rem == 1) {
            return n + 2;
        } else if (rem == 2) {
            return n + 2;
        } else { // rem == 3
            return n - 1;
        }
    }
}
```
### Algorithm
*   If `n` is 1 or 2, return `n`.
*   If `n` is 3, return 6.
*   If `n` is 4, return 7.
*   If `n > 4`:
    *   Calculate `n % 4`.
    *   If `n % 4 == 0`, return `n + 1`.
    *   If `n % 4 == 1`, return `n + 2`.
    *   If `n % 4 == 2`, return `n + 2`.
    *   If `n % 4 == 3`, return `n - 1`.

# Solutions
### Java

```java
class Solution {
public
  int clumsy(int N) {
    Deque<Integer> s = new ArrayDeque<>();
    s.offerLast(N);
    int op = 0;
    for (int i = N - 1; i > 0; --i) {
      if (op == 0) {
        s.offerLast(s.pollLast() * i);
      } else if (op == 1) {
        s.offerLast(s.pollLast() / i);
      } else if (op == 2) {
        s.offerLast(i);
      } else {
        s.offerLast(-i);
      }
      op = (op + 1) % 4;
    }
    int res = 0;
    while (!s.isEmpty()) {
      res += s.pollLast();
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int clumsy(int n) {
    stack<int> stk;
    stk.push(n);
    int k = 0;
    for (int x = n - 1; x; --x) {
      if (k == 0) {
        stk.top() *= x;
      } else if (k == 1) {
        stk.top() /= x;
      } else if (k == 2) {
        stk.push(x);
      } else {
        stk.push(-x);
      }
      k = (k + 1) % 4;
    }
    int ans = 0;
    while (!stk.empty()) {
      ans += stk.top();
      stk.pop();
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def clumsy(self, N: int) -> int: op = 0 s = [N] for i in range(N - 1, 0, - 1): if op == 0: s . append(s . pop() * i) elif op == 1: s . append(int(s . pop() / i)) elif op == 2: s . append(i) else: s . append(- i) op = (op + 1) % 4 return sum(s)

```