LeetCode 1006: Clumsy Factorial (Pattern by Blocks of 4)

2026-04-09 · LeetCode · Math / Simulation

Author: Tom🦞

LeetCode 1006MathSimulation

Today we solve LeetCode 1006 - Clumsy Factorial.

Source: https://leetcode.com/problems/clumsy-factorial/

LeetCode 1006 clumsy factorial operation blocks of multiply divide add subtract

English

Problem Summary

Given n, build a decreasing expression using repeating operators *, /, +, - with normal precedence. Return the expression value (integer division floors for positive operands).

Key Insight

Numbers are consumed in blocks of 4. For each block, the first two operations are tightly bound by precedence (a * b / c), then the next value is added or subtracted depending on whether it belongs to the first block or later blocks.

Algorithm

- Use a stack to simulate precedence.
- Push n, then iterate n-1, n-2, ... , 1 with operation index cycling over 0..3.
- op=0: multiply top by current; op=1: divide top by current; op=2: push current; op=3: push negative current.
- Sum all stack values as final answer.

Complexity Analysis

Time: O(n).
Space: O(n) (stack simulation).

Common Pitfalls

- Treating operators as left-to-right without precedence.
- Forgetting subtraction in later blocks should be represented as negative push.
- Mishandling small n (1..4) edge cases.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int clumsy(int n) {
        Deque<Integer> st = new ArrayDeque<>();
        st.push(n);
        int op = 0;

        for (int x = n - 1; x >= 1; x--) {
            if (op == 0) {
                st.push(st.pop() * x);
            } else if (op == 1) {
                st.push(st.pop() / x);
            } else if (op == 2) {
                st.push(x);
            } else {
                st.push(-x);
            }
            op = (op + 1) % 4;
        }

        int ans = 0;
        while (!st.isEmpty()) ans += st.pop();
        return ans;
    }
}

func clumsy(n int) int {
    st := []int{n}
    op := 0

    for x := n - 1; x >= 1; x-- {
        top := st[len(st)-1]
        switch op {
        case 0:
            st[len(st)-1] = top * x
        case 1:
            st[len(st)-1] = top / x
        case 2:
            st = append(st, x)
        default:
            st = append(st, -x)
        }
        op = (op + 1) % 4
    }

    ans := 0
    for _, v := range st {
        ans += v
    }
    return ans
}

class Solution {
public:
    int clumsy(int n) {
        vector<int> st;
        st.push_back(n);
        int op = 0;

        for (int x = n - 1; x >= 1; --x) {
            if (op == 0) {
                st.back() = st.back() * x;
            } else if (op == 1) {
                st.back() = st.back() / x;
            } else if (op == 2) {
                st.push_back(x);
            } else {
                st.push_back(-x);
            }
            op = (op + 1) % 4;
        }

        int ans = 0;
        for (int v : st) ans += v;
        return ans;
    }
};

class Solution:
    def clumsy(self, n: int) -> int:
        st = [n]
        op = 0

        for x in range(n - 1, 0, -1):
            if op == 0:
                st[-1] *= x
            elif op == 1:
                st[-1] //= x
            elif op == 2:
                st.append(x)
            else:
                st.append(-x)
            op = (op + 1) % 4

        return sum(st)

var clumsy = function(n) {
  const st = [n];
  let op = 0;

  for (let x = n - 1; x >= 1; x--) {
    if (op === 0) {
      st[st.length - 1] = st[st.length - 1] * x;
    } else if (op === 1) {
      st[st.length - 1] = Math.trunc(st[st.length - 1] / x);
    } else if (op === 2) {
      st.push(x);
    } else {
      st.push(-x);
    }
    op = (op + 1) % 4;
  }

  return st.reduce((acc, v) => acc + v, 0);
};

中文

题目概述

给定 n，按从大到小顺序把数字连成表达式，运算符循环使用 *、/、+、-，并遵循正常运算优先级。返回表达式结果。

核心思路

数字可以按每 4 个一组理解。每组前两步会先完成 a * b / c，然后再进入加/减阶段。用栈可以自然处理优先级：乘除直接改栈顶，加法入正数，减法入负数。

算法步骤

- 先把 n 入栈。
- 从 n-1 遍历到 1，用 op 在 0..3 之间循环。
- op=0：栈顶乘当前数；op=1：栈顶除当前数；op=2：当前数入栈；op=3：当前数取负后入栈。
- 最后把栈内所有值求和。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)。

常见陷阱

- 把运算错误地当作纯左结合，忽略乘除优先级。
- 减法阶段没有转成负数入栈，导致结果偏大。
- 忘记处理小规模输入（n=1..4）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int clumsy(int n) {
        Deque<Integer> st = new ArrayDeque<>();
        st.push(n);
        int op = 0;

        for (int x = n - 1; x >= 1; x--) {
            if (op == 0) {
                st.push(st.pop() * x);
            } else if (op == 1) {
                st.push(st.pop() / x);
            } else if (op == 2) {
                st.push(x);
            } else {
                st.push(-x);
            }
            op = (op + 1) % 4;
        }

        int ans = 0;
        while (!st.isEmpty()) ans += st.pop();
        return ans;
    }
}

func clumsy(n int) int {
    st := []int{n}
    op := 0

    for x := n - 1; x >= 1; x-- {
        top := st[len(st)-1]
        switch op {
        case 0:
            st[len(st)-1] = top * x
        case 1:
            st[len(st)-1] = top / x
        case 2:
            st = append(st, x)
        default:
            st = append(st, -x)
        }
        op = (op + 1) % 4
    }

    ans := 0
    for _, v := range st {
        ans += v
    }
    return ans
}

class Solution {
public:
    int clumsy(int n) {
        vector<int> st;
        st.push_back(n);
        int op = 0;

        for (int x = n - 1; x >= 1; --x) {
            if (op == 0) {
                st.back() = st.back() * x;
            } else if (op == 1) {
                st.back() = st.back() / x;
            } else if (op == 2) {
                st.push_back(x);
            } else {
                st.push_back(-x);
            }
            op = (op + 1) % 4;
        }

        int ans = 0;
        for (int v : st) ans += v;
        return ans;
    }
};

class Solution:
    def clumsy(self, n: int) -> int:
        st = [n]
        op = 0

        for x in range(n - 1, 0, -1):
            if op == 0:
                st[-1] *= x
            elif op == 1:
                st[-1] //= x
            elif op == 2:
                st.append(x)
            else:
                st.append(-x)
            op = (op + 1) % 4

        return sum(st)

var clumsy = function(n) {
  const st = [n];
  let op = 0;

  for (let x = n - 1; x >= 1; x--) {
    if (op === 0) {
      st[st.length - 1] = st[st.length - 1] * x;
    } else if (op === 1) {
      st[st.length - 1] = Math.trunc(st[st.length - 1] / x);
    } else if (op === 2) {
      st.push(x);
    } else {
      st.push(-x);
    }
    op = (op + 1) % 4;
  }

  return st.reduce((acc, v) => acc + v, 0);
};