Get started

Clumsy Factorial — Medium Problem & Solution

The clumsy factorial of n replaces the multiplications of n!

  • Difficulty: Medium
  • Topics: Math, Simulation, Stack
  • Asked at: Amazon, Adobe, Oracle
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The clumsy factorial of n replaces the multiplications of n! with a rotating sequence of operators — multiply, floor-divide, add, subtract — applied to the descending run n, n-1, …, 1.

For example clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1. Multiplication and division bind tighter than addition and subtraction, and division truncates towards zero.

Return the value.

Example 1

Input: n = 4
Output: 7
Explanation: 4 * 3 / 2 + 1 = 6 + 1 = 7.

Example 2

Input: n = 10
Output: 12
Explanation: 11 + 7 - 7 + 3 - 2 = 12, where 90 / 8 is 11 and 30 / 4 is 7.

Example 3

Input: n = 1
Output: 1

Constraints

  • 1 <= n <= 10000

How to solve Clumsy Factorial

Treat the expression as a sum of signed terms. Multiplication and division modify the term currently on top of the stack; addition and subtraction start a new term, negated for subtraction. Summing the stack at the end applies precedence correctly.

Approach

  1. Push n and set the operator index to 0 (multiply).
  2. For x from n - 1 down to 1, apply the current operator: multiply or divide the stack top, or push x (for +) or -x (for -).
  3. Advance the operator cyclically through * / + -.
  4. Return the sum of the stack.

Why it works

Higher-precedence operators must be resolved before the sum, which is exactly what folding them into the top of the stack does. Encoding subtraction as a negative term means the final combination is a plain sum, which is associative and needs no further ordering.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Division must truncate towards zero, which is what C, Java, Go and Rust do natively but Python's // and Ruby's / do not — a negative term needs an explicit sign-aware division there.
  • Evaluating strictly left to right ignores precedence and gives the wrong answer from n = 5 upward.
  • The operator cycle starts at multiply, not add.

Reference solution

Python

def clumsy(n: int) -> int:
    def trunc(a: int, b: int) -> int:
        q = abs(a) // abs(b)
        return -q if (a < 0) != (b < 0) else q

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

JavaScript

var clumsy = function(n) {
    var trunc = function(a, b) {
        var q = Math.floor(Math.abs(a) / Math.abs(b));
        return ((a < 0) !== (b < 0)) ? -q : q;
    };
    var stack = [n];
    var op = 0;
    for (var x = n - 1; x >= 1; x--) {
        if (op === 0) stack[stack.length - 1] = stack[stack.length - 1] * x;
        else if (op === 1) stack[stack.length - 1] = trunc(stack[stack.length - 1], x);
        else if (op === 2) stack.push(x);
        else stack.push(-x);
        op = (op + 1) % 4;
    }
    var total = 0;
    for (var i = 0; i < stack.length; i++) total += stack[i];
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue