Clumsy Factorial

medium stack math simulation

Problem

The clumsy factorial of a positive integer N takes the numbers N, N-1, N-2, ..., 1 and joins them with the operations multiply, divide, add, subtract repeating in that fixed order. The operations keep their usual precedence — multiplication and division are evaluated left to right before addition and subtraction — and integer division uses floor (truncating toward zero for positive operands). Return the value of the clumsy factorial.

InputN = 4

Output7

4 * 3 / 2 + 1 = 6 + 1 = 7.

def clumsy(n):
    stack = [n]
    op = 0  # 0:*  1:/  2:+  3:-
    for x in range(n - 1, 0, -1):
        if op == 0:
            stack.append(stack.pop() * x)
        elif op == 1:
            top = stack.pop()
            stack.append(int(top / x))
        elif op == 2:
            stack.append(x)
        else:
            stack.append(-x)
        op = (op + 1) % 4
    return sum(stack)

function clumsy(n) {
  const stack = [n];
  let op = 0; // 0:*  1:/  2:+  3:-
  for (let x = n - 1; x > 0; x--) {
    if (op === 0) stack.push(stack.pop() * x);
    else if (op === 1) {
      const top = stack.pop();
      stack.push(Math.trunc(top / x));
    } else if (op === 2) stack.push(x);
    else stack.push(-x);
    op = (op + 1) % 4;
  }
  return stack.reduce((a, b) => a + b, 0);
}

class Solution {
    public int clumsy(int n) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(n);
        int op = 0; // 0:*  1:/  2:+  3:-
        for (int x = n - 1; x > 0; x--) {
            if (op == 0) stack.push(stack.pop() * x);
            else if (op == 1) stack.push(stack.pop() / x);
            else if (op == 2) stack.push(x);
            else stack.push(-x);
            op = (op + 1) % 4;
        }
        int sum = 0;
        for (int v : stack) sum += v;
        return sum;
    }
}

int clumsy(int n) {
    vector<int> stack{n};
    int op = 0; // 0:*  1:/  2:+  3:-
    for (int x = n - 1; x > 0; x--) {
        if (op == 0) { int t = stack.back(); stack.back() = t * x; }
        else if (op == 1) { int t = stack.back(); stack.back() = t / x; }
        else if (op == 2) stack.push_back(x);
        else stack.push_back(-x);
        op = (op + 1) % 4;
    }
    int sum = 0;
    for (int v : stack) sum += v;
    return sum;
}

Explanation

The numbers N, N-1, ..., 1 are joined by the operators * / + - repeating in that order, and we must respect precedence — multiply and divide before add and subtract. A stack handles this cleanly by applying high-precedence ops right away and deferring the low-precedence ones.

We start with N on the stack and cycle op through 0,1,2,3 meaning * / + -. For * we pop the top and push top * x. For / we pop and push trunc(top / x). These both act on the stack top immediately.

For + we just push x, and for - we push -x. We defer these because addition and subtraction come last — by storing them as signed values, the final answer is simply the sum of the whole stack.

Example: N = 4 gives 4 * 3 / 2 + 1. Push 4; *3 → 12; /2 → 6; then +1 pushes 1. Stack is [6, 1], and the sum is 7.

Each number is processed once, so the algorithm runs in linear time.

Time: O(n) Space: O(n)