> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/array_and_numbers/clumsy-factorial.md).

# 1006. Clumsy Factorial

Normally, 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 instead make a *clumsy factorial:* using the integers in decreasing order, we swap out the multiply operations for a fixed rotation of operations: 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` equals `11`.  This guarantees the result is an integer.

`Implement the clumsy` function as defined above: given an integer `N`, it returns the clumsy factorial of `N`.

**Example 1:**

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

**Example 2:**

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

**Note:**

1. `1 <= N <= 10000`
2. `-2^31 <= answer <= 2^31 - 1`  (The answer is guaranteed to fit within a 32-bit integer.)

## Thoughts

求N的阶乘，只是乘要依次换成\*/+-。观察到i \* (i-1) / (i-2) = i+1，当 i >= 5时，因此

```
i * (i-1) / (i-2) + (i-3) - (i-4) * (i-5) / (i-6) + (i-7) - (i-8) * .... + rest elements=   (i+1) + "(i-3)" - "(i-4) * (i-5) / (i-6)" + "(i-7)" - "(i-8) * " .... + rest elements=   (i+1) + "(i-3) - (i-3)" + "(i-7) - (i-7)" +  ....  + rest elements=   (i+1) + rest elements
```

每四个元素看成一组，于是有以下四种情况：

1. when 0 element left: final result is (i+1) + ... + 5 - (4\*3/2) + 1, which is i+1
2. when 1 element left: final result is (i+1) + ... + 6 - (5\*4/3) + 2 - 1, which is i+2
3. when 2 element left: final result is (i+1) + ... + 7 - (6\*5/4) + 3 - 2 \* 1, which is i+2
4. when 3 element left: final result is (i+1) + ... + 8 - (7\*6/5) + 4 - 3 \* 2 / 1, which is i-1

因此分类讨论。参考自[这](https://leetcode.com/problems/clumsy-factorial/discuss/252279/You-never-think-of-this-amazing-O\(1\)-solution)。

## Code

```python
class Solution:
    def clumsy(self, N: int) -> int:
        if N <= 2: return N
        if N <= 4: return N + 3
        if N % 4 == 0: return N + 1
        elif N % 4 <= 2: return N + 2
        else: return N - 1
            
```

```cpp
class Solution {
public:
    int clumsy(int N) {
        int i = N;
        int res = 0;
        for (; i >= 4; i -= 4) {
            int r = i * (i - 1) / (i - 2);
            res += i == N ? r : -r;
            res += (i - 3);
        }

        int r = 0;
        if (i >= 1) {
            int r = i * ((i - 1) >= 1 ? i - 1 : 1) / ((i - 2) >= 1 ? i - 2 : 1);
            res += i == N ? r : -r;
        }
        return res;
    }
};
```