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 <= 10^4

Solution

Method 1 – Stack Simulation

Intuition

Simulate the clumsy factorial by rotating through the operations (*, //, +, -) and using a stack to handle operator precedence. This approach mimics the order of operations and ensures correct calculation for each step.

Approach

Initialize a stack with n.
For each number from n-1 down to 1, apply the next operation in the sequence (*, //, +, -).
For *, //, operate on the top of the stack. For +, push the number. For -, push -number.
At the end, sum the stack for the result.

Complexity

⏰ Time complexity: O(n), because we process each number from n down to 1 exactly once, and each stack operation is O(1).
🧺 Space complexity: O(n), since the stack can grow up to size n in the worst case (when all operations are + or -).

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int clumsy(int n) {\n        vector<int> stk{n};\n        int op = 0;\n        for (int i = n - 1; i > 0; --i, ++op) {\n            if (op % 4 == 0) stk.back() *= i;\n            else if (op % 4 == 1) stk.back() /= i;\n            else if (op % 4 == 2) stk.push_back(i);\n            else stk.push_back(-i);\n        }\n        return accumulate(stk.begin(), stk.end(), 0);\n    }\n};","lang":"cpp"},{"language":"Go","code":"type Solution struct{}\nfunc (Solution) Clumsy(n int) int {\n    stk := []int{n}\n    n--\n    op := 0\n    for n > 0 {\n        switch op % 4 {\n        case 0:\n            stk[len(stk)-1] *= n\n        case 1:\n            stk[len(stk)-1] /= n\n        case 2:\n            stk = append(stk, n)\n        default:\n            stk = append(stk, -n)\n        }\n        n--\n        op++\n    }\n    ans := 0\n    for _, v := range stk {\n        ans += v\n    }\n    return ans\n}","lang":"go"},{"language":"Java","code":"class Solution {\n    public int clumsy(int n) {\n        Stack<Integer> stk = new Stack<>();\n        stk.push(n);\n        n--;\n        int op = 0;\n        while (n > 0) {\n            if (op % 4 == 0) stk.push(stk.pop() * n);\n            else if (op % 4 == 1) stk.push(stk.pop() / n);\n            else if (op % 4 == 2) stk.push(n);\n            else stk.push(-n);\n            n--;\n            op++;\n        }\n        int ans = 0;\n        while (!stk.isEmpty()) ans += stk.pop();\n        return ans;\n    }\n}","lang":"java"},{"language":"Kotlin","code":"class Solution {\n    fun clumsy(n: Int): Int {\n        val stk = mutableListOf(n)\n        var num = n - 1\n        var op = 0\n        while (num > 0) {\n            when (op % 4) {\n                0 -> stk[stk.lastIndex] = stk.last() * num\n                1 -> stk[stk.lastIndex] = stk.last() / num\n                2 -> stk.add(num)\n                else -> stk.add(-num)\n            }\n            num--\n            op++\n        }\n        return stk.sum()\n    }\n}","lang":"kotlin"},{"language":"Python","code":"class Solution:\n    def clumsy(self, n: int) -> int:\n        ops = ['*', '//', '+', '-']\n        stack = [n]\n        n -= 1\n        idx = 0\n        while n > 0:\n            op = ops[idx % 4]\n            if op == '*':\n                stack[-1] *= n\n            elif op == '//':\n                stack[-1] = int(stack[-1] / n)\n            elif op == '+':\n                stack.append(n)\n            else:\n                stack.append(-n)\n            n -= 1\n            idx += 1\n        return sum(stack)","lang":"python"},{"language":"Rust","code":"impl Solution {\n    pub fn clumsy(n: i32) -> i32 {\n        let mut stk = vec![n];\n        let mut num = n

Related Tags