What exactly is the clumsy factorial pattern?

The clumsy factorial uses a fixed operation rotation of '*', '/', '+', '-' applied to numbers from n down to 1 while respecting left-to-right multiplication and division before addition and subtraction.

Can I implement clumsy factorial without a stack?

Yes, but careful management of intermediate results and operation order is required to maintain correct arithmetic precedence.

What are common mistakes when computing clumsy factorial?

Common errors include misapplying operation order, breaking the operation rotation, and mishandling subtraction in the middle of the sequence.

How do I handle division in clumsy factorial?

Division should be integer division and applied immediately in left-to-right order before any addition or subtraction steps.

Is clumsy factorial useful in coding interviews?

Yes, it tests stack-based state management, simulation of operation sequences, and precise handling of arithmetic order.

#1006

Medium

auto_awesome栈·状态

LeetCode 题解工作台

笨阶乘

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如， factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 。相反，我们设计了一个笨阶乘 clumsy ：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操…

数学栈模拟

题目描述

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1。

相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。

例如，clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

示例 1：

输入：4
输出：7
解释：7 = 4 * 3 / 2 + 1

示例 2：

输入：10
输出：12
解释：12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

提示：

1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1 （答案保证符合 32 位整数。）

lightbulb

解题思路

方法一：栈 + 模拟

笨阶乘的计算过程可以看作是一个栈的模拟过程。

我们定义一个栈 stk，初始时我们将 $n$ 入栈，定义一个变量 $k$ ，表示当前的操作符，初始时 $k = 0$ 。

然后我们从 $n-1$ 开始，枚举 $x$ ，根据当前的 $k$ 的值，决定如何处理 $x$ ：

当 $k = 0$ 时，表示乘法操作，我们将栈顶元素出栈，与 $x$ 相乘后再入栈；
当 $k = 1$ 时，表示除法操作，我们将栈顶元素出栈，与 $x$ 相除后取整数部分再入栈；
当 $k = 2$ 时，表示加法操作，我们直接将 $x$ 入栈；
当 $k = 3$ 时，表示减法操作，我们将 $-x$ 入栈。

接着我们更新 $k = (k + 1) \mod 4$ 。

最后，我们将栈中的元素累加即为答案。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为题目给定的整数 $N$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def clumsy(self, n: int) -> int:
        k = 0
        stk = [n]
        for x in range(n - 1, 0, -1):
            if k == 0:
                stk.append(stk.pop() * x)
            elif k == 1:
                stk.append(int(stk.pop() / x))
            elif k == 2:
                stk.append(x)
            else:
                stk.append(-x)
            k = (k + 1) % 4
        return sum(stk)

speed

复杂度分析

指标	值
时间	complexity is O(n) because each number from n to 1 is processed once, and each stack operation is O(1). Space complexity is O(n) in the worst case due to storing intermediate results in the stack.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if the candidate respects left-to-right multiplication/division precedence before addition/subtraction.
question_mark
Look for efficient stack usage to avoid recalculating intermediate results multiple times.
question_mark
Observe whether the rotation of operations is correctly implemented and cycled through.

warning

常见陷阱

外企场景

error
Failing to apply multiplication and division left to right before addition and subtraction.
error
Incorrectly handling the operation rotation, especially after the first cycle.
error
Attempting recursive factorial computation without considering operation order, leading to wrong results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute clumsy factorial for a subset of numbers with custom operation sequences.
arrow_right_alt
Implement the clumsy factorial using recursion instead of stack simulation.
arrow_right_alt
Optimize space by using variables instead of a stack to track intermediate results.

help

常见问题

外企场景

继续练习

#1041 困于环中的机器人 #946 验证栈序列 #1103 分糖果 II