We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Clumsy Factorial

Number: 1048

Difficulty: Medium

Paid? No

Companies: Amazon, Microsoft

Problem Description

Given a positive integer n, compute its clumsy factorial. Instead of the normal factorial multiplication, the numbers are processed in descending order with operators in a fixed cycle: multiply (*), divide (/), add (+), subtract (-). Note that multiplication and division have precedence over addition and subtraction, and division is done via floor division.

Key Insights

  • The operations cycle in a fixed order: multiply, divide, add, subtract.
  • Multiplication and division are performed immediately (following standard precedence) to form groups.
  • A stack can be used to handle the addition and subtraction parts by pushing intermediate results.
  • Process the numbers in a simulation loop, applying operations based on the index in the cycle.

Space and Time Complexity

Time Complexity: O(n), as we iterate from n down to 1.
Space Complexity: O(n) in the worst case for the stack, though the additional space may be optimized.

Solution

The solution simulates the clumsy factorial by using a stack data structure. Start by pushing the first number n onto the stack. Then iterate over the remaining numbers in descending order. Use an index modulo operation to determine which operation to perform:

  • For multiplication and division (which have high precedence), combine the current number with the top of the stack.
  • For addition, push the current number onto the stack.
  • For subtraction, push the negative of the current number onto the stack. After processing all numbers, sum the elements in the stack to get the final result.

Code Solutions

# Function to compute the clumsy factorial
def clumsy(n: int) -> int:
    # Initialize a stack with the first number
    stack = [n]
    # Counter to cycle through operations: 0: multiply, 1: divide, 2: add, 3: subtract
    operation_index = 0
    # Decrease n for the next number in the sequence
    n -= 1

    # Process remaining numbers in descending order
    while n > 0:
        if operation_index % 4 == 0:
            # Multiply: combine with top of the stack
            stack[-1] = stack[-1] * n
        elif operation_index % 4 == 1:
            # Divide: apply integer (floor) division on the top element
            stack[-1] = int(stack[-1] / n)
        elif operation_index % 4 == 2:
            # Addition: push the current number onto the stack
            stack.append(n)
        else:
            # Subtraction: push the negative of the current number
            stack.append(-n)
        operation_index += 1
        n -= 1

    # Sum up the values in the stack to get the clumsy factorial
    return sum(stack)

# Example usage:
print(clumsy(4))   # Output: 7
print(clumsy(10))  # Output: 12
← Back to All Questions