1006. Clumsy Factorial Medium

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

Approach

Input: A positive integer n

Output: Return the Clumsy Factorial of n

This problem belongs to the classic application of Expression Evaluation + Stack.

The clumsy factorial operation follows a fixed 4-step rotation: * → / → + → -, evaluated sequentially for every group of four descending numbers.

We can use a stack stack to simulate the entire evaluation process:

• For * and / operations: Pop the top element from the stack, perform the operation with the current number, and push the result back onto the stack;
• For the + operation: Push the current number directly onto the stack;
• For the - operation: Push the negated current number onto the stack, which is equivalent to performing subtraction later.

Finally, calculate the sum of all elements in the stack to get the final result.

Implementation

python

class Solution:
    def clumsy(self, n: int) -> int:
        stack = [n]  # Use a stack to save results, initially pushing the first number
        n -= 1
        index = 0  # Used to track the current operation: 0 for *, 1 for /, 2 for +, 3 for -, looping.

        while n > 0:
            if index % 4 == 0:
                # Multiplication
                stack[-1] *= n
            elif index % 4 == 1:
                # Division (Python defaults to float division, we need integer truncation division towards zero)
                stack[-1] = int(stack[-1] / n)
            elif index % 4 == 2:
                # Addition, directly push
                stack.append(n)
            else:
                # Subtraction, push a negative number
                stack.append(-n)
            n -= 1
            index += 1

        return sum(stack)

javascript

/**
 * @param {number} n
 * @return {number}
 */
const clumsy = function(n) {
    const stack = [n];
    n -= 1;
    let index = 0;

    while (n) {
        if (index % 4 == 0) {
            const top = stack.pop();
            stack.push(top * n);
        } else if (index % 4 == 1) {
            const top = stack.pop();
            stack.push(parseInt(top / n));
        } else if (index % 4 == 2) {
            stack.push(n);
        } else {
            stack.push(-n);
        }

        n --;
        index ++;
    }

    return stack.reduce((acc, curr) => acc + curr, 0);
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

1006. Clumsy Factorial (English)

1006. 笨阶乘 (Chinese)