Scale Engineer

Clumsy Factorial

Med
#0960Time: O(N), as we iterate through the numbers from `n` to 1 once. The final summation also takes O(N) in the worst case.Space: O(N), as the stack can store up to `n/4 + 1` terms in the worst case, which is proportional to `n`.
Patterns
Math
Data structures
Stack

Prompt

The factorial of a positive integer n is the product of all positive integers less than or equal to n.

  • For example, factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.

We make a clumsy factorial using the integers in decreasing order by swapping out the multiply operations for a fixed rotation of operations with multiply '*', divide '/', add '+', and subtract '-' in this order.

  • For example, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1.

However, these operations are still applied using the usual order of operations of arithmetic. We do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.

Additionally, the division that we use is floor division such that 10 * 9 / 8 = 90 / 8 = 11.

Given an integer n, return the clumsy factorial of n.

 

Example 1:

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

Example 2:

Input: n = 10
Output: 12
Explanation: 12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

 

Constraints:

  • 1 <= n <= 104

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the evaluation of the clumsy factorial expression. Due to the standard order of operations (PEMDAS/BODMAS), where multiplication and division have higher precedence than addition and subtraction, a stack is a natural data structure to use. We can process the numbers from n down to 1, performing multiplications and divisions immediately on the top of the stack, while deferring additions and subtractions by pushing new terms onto the stack. The final result is the sum of all numbers left in the stack.

Algorithm

  • Handle base cases for n <= 2 by returning n.
  • Initialize an empty stack of integers.
  • Push the first number, n, onto the stack.
  • Initialize an operation counter, op_idx = 0.
  • Loop for i from n-1 down to 1:
    • If op_idx % 4 == 0 (multiplication): Pop from the stack, multiply by i, and push the result.
    • If op_idx % 4 == 1 (division): Pop from the stack, divide by i, and push the result.
    • If op_idx % 4 == 2 (addition): Push i onto the stack.
    • If op_idx % 4 == 3 (subtraction): Push -i onto the stack.
    • Increment op_idx.
  • After the loop, calculate the sum of all elements in the stack and return it.

Walkthrough

We iterate from n down to 1, keeping track of the current operation in the cycle *, /, +, -. A stack is used to store the intermediate terms that will eventually be summed up. When we encounter a * or / operation, we apply it to the last term we were calculating, which is conveniently at the top of the stack. We pop the value, perform the operation with the current number, and push the result back. When we encounter a + or - operation, it signals the end of the previous term and the beginning of a new one. We simply push the current number (or its negation for -) onto the stack as a new term. After iterating through all the numbers, the stack contains all the terms of the expression (e.g., for n=10, it would hold [11, 7, -7, 3, -2]). The final step is to sum up all the values in the stack to get the answer.

For example, with n=4 (4 * 3 / 2 + 1):

  1. Push 4. Stack: [4]
  2. Op is *. Pop 4, push 4 * 3 = 12. Stack: [12]
  3. Op is /. Pop 12, push 12 / 2 = 6. Stack: [6]
  4. Op is +. Push 1. Stack: [6, 1]
  5. Sum stack: 6 + 1 = 7.
import java.util.Stack; class Solution {    public int clumsy(int n) {        if (n <= 2) {            return n;        }                Stack<Integer> stack = new Stack<>();        stack.push(n);                int op = 0; // 0:*, 1:/, 2:+, 3:-        for (int i = n - 1; i > 0; i--) {            if (op % 4 == 0) { // *                stack.push(stack.pop() * i);            } else if (op % 4 == 1) { // /                stack.push(stack.pop() / i);            } else if (op % 4 == 2) { // +                stack.push(i);            } else { // -                stack.push(-i);            }            op++;        }                int result = 0;        while (!stack.isEmpty()) {            result += stack.pop();        }                return result;    }}

Complexity

Time

O(N), as we iterate through the numbers from `n` to 1 once. The final summation also takes O(N) in the worst case.

Space

O(N), as the stack can store up to `n/4 + 1` terms in the worst case, which is proportional to `n`.

Trade-offs

Pros

  • Conceptually straightforward and directly models the expression evaluation process.

  • Easy to implement and debug.

Cons

  • Uses extra space for the stack, which is not optimal compared to other approaches.

Solutions

class Solution {public  int clumsy(int N) {    Deque<Integer> s = new ArrayDeque<>();    s.offerLast(N);    int op = 0;    for (int i = N - 1; i > 0; --i) {      if (op == 0) {        s.offerLast(s.pollLast() * i);      } else if (op == 1) {        s.offerLast(s.pollLast() / i);      } else if (op == 2) {        s.offerLast(i);      } else {        s.offerLast(-i);      }      op = (op + 1) % 4;    }    int res = 0;    while (!s.isEmpty()) {      res += s.pollLast();    }    return res;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem