Clumsy Factorial

Medium
706.

Clumsy Factorial

Clumsy Factorial is a medium coding problem on math, simulation and stack, asked in Amazon, Adobe and Oracle interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var clumsy = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Clumsy Factorial — Solution in Python, Java & C++

Clumsy Factorial solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on math and simulation.

Clumsy Factorial is a medium coding problem on math, simulation and stack, asked in Amazon, Adobe and Oracle interviews.

  • 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

Hints for Clumsy Factorial

  1. Hint 1

    Evaluate with a stack: push terms, and fold * and / into the top of the stack immediately.

  2. Hint 2

    A + pushes the value, a - pushes its negation — then the final answer is the sum of the stack.

  3. Hint 3

    That reproduces operator precedence without parsing anything.

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)

Java

public static int clumsy(int n) {
    List<Long> stack = new ArrayList<>();
    stack.add((long) n);
    int op = 0;
    for (int x = n - 1; x >= 1; x--) {
        int last = stack.size() - 1;
        if (op == 0) stack.set(last, stack.get(last) * x);
        else if (op == 1) stack.set(last, stack.get(last) / x);
        else if (op == 2) stack.add((long) x);
        else stack.add((long) -x);
        op = (op + 1) % 4;
    }
    long total = 0;
    for (long v : stack) total += v;
    return (int) total;
}

C++

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

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Stack Data Structure