Rotating Factorial Microsoft Python Interview Question

Before, you work on this question, make sure you've solved the easier warmup problem Factorial Formula, where you need to write a function to compute $n$ factorial as follows:

$n! = n * (n-1) * (n-2) * ..... 2 * 1$.

Now that you know the factorial formula, let's define a rotating factorial: instead of multiplying out all the numbers, we rotate between arithmetic operators like multiplication (), floor division (), addition (), and subtraction ().

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

When computing the above equation remember to apply PEMDAS (the order of operations) where multiplication and floor division come before addition/subtraction.

p.s. floor division is a type of division operation that returns the largest integer less than or equal to the result of dividing two numbers (aka we chop off the remainder and return a whole integer).

Floor Division Example: $13 // 4 = 3$

Simulation using stack

One way to solve this problem is by simulating a series of operations (multiply, divide, add, subtract) while managing the results step-by-step using a stack. But why do we need a stack?

When we perform operations like multiplication or division, we need to make sure that the previous results are correctly applied before moving on to the next number. A stack helps us manage this process efficiently by allowing us to "store" intermediate results and apply them in the correct order.

For example, when you multiply a number and get a result, you need to save that result before moving on to the next operation. If we didn’t use a stack, it would be harder to keep track of previous results and the order of operations would get confusing. Stacks allow us to easily push results in and later pop them out in the right sequence.

Let’s walk through an example using :

1. Start with $n = 10$: We’ll first push onto the stack:
   • stack = [10]
2. Multiply ($10 * 9 = 90$): We remove () from the stack, multiply it by , and push the result () back:
   • stack = [90]
3. Divide ($90 // 8 = 11$): Next, we remove , divide it by , and push the result () back:
   • stack = [11]
4. Add : Simply push onto the stack:
   • stack = [11, 7]
5. Subtract : For subtraction, we push (negative value):
   • stack = [11, 7, -6]
6. Multiply ($-6 * 5 = -30$): Remove , multiply it by , and push back:
   • stack = [11, 7, -30]
7. Divide ($-30 // 4 = -7$): Remove , divide by , and push :
   • stack = [11, 7, -7]
8. Add : Push :
   • stack = [11, 7, -7, 3]
9. Subtract : Push :
   • stack = [11, 7, -7, 3, -2]

Finally, we add up everything in the stack:

$11 + 7 - 7 + 3 - 2 = 12$

How do we alternate between operations?

The operations follow a cycle: multiply, divide, add, subtract. Once we reach the last operation (subtract), we go back to the first one (multiply). To keep track of this, we use a number that cycles between 0 and 3.

We use a variable called to keep track of which operation we’re currently on (multiply, divide, add, or subtract). Instead of applying modulo directly when checking each operation, we check the value of and then cycle through the operations by updating at the end of each iteration using modulo.

Here’s how it works:

• Multiply when
• Divide when
• Add when
• Subtract when

After each operation, we move to the next number and increase the variable. We use at the end of each iteration to ensure the value of resets after (when ), so it goes back to (), and the cycle continues.

This way, we loop through the four operations in the right order, starting with multiply, divide, add, and then subtract, before repeating the cycle.

Here is the full code:

Optimized Approach

If we write down the operations for a few numbers, we can observe a clear pattern. Let’s calculate the clumsy factorial for a few values:

1. For ( n = 12 ),
   $12 * 11 / 10 + 9 - 8 * 7 / 6 + 5 - 4 * 3 / 2 + 1 = 13 + 9 - 9 + 5 - 6 + 1 = 13$ (which is n + 1)

2. For ( n = 11 ),
   $11 * 10 / 9 + 8 - 7 * 6 / 5 + 4 - 3 * 2 / 1 = 12 + 8 - 8 + 4 - 6 = 10$ (which is n - 1)

3. For ( n = 10 ),
   $10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1 = 11 + 7 - 7 + 3 - 2 = 12$ (which is n + 2)

4. For ( n = 9 ),
   $9 * 8 / 7 + 6 - 5 * 4 / 3 + 2 - 1 = 10 + 6 - 6 + 2 - 1 = 11$ (which is n + 2)

When you compute this for $n = 8$, you’ll see a similar pattern to $n = 12$, and for $n = 7$, you'll observe the same as $n = 11$.

The reason for this repeating pattern lies in the number of operations (multiplication, division, addition, and subtraction) and the number of terms remaining. Since the operations repeat in cycles of four (due to the four basic arithmetic operations), the result will fall into specific predictable outcomes based on the remainder when is divided by . This can be related to modulo arithmetic, which helps us keep track of where we are in the cycle of operations.

• When ( n % 4 == 0 ), the result will be ( n + 1 ).
• When ( n % 4 == 3 ), the result will be ( n - 1 ).
• Otherwise, the result will be ( n + 2 ).

Finally, when ( n ) is less than or equal to 4, we have some edge cases:

• For $n = 4$, the operations work out to $4 * 3 / 2 + 1 = 7$.
• For $n = 3$, it's $3 * 2 / 1 = 6$.
• For $n = 2$, the result is simply $2$.
• For $n = 1$, it’s just $1$.

Now that we’ve established the pattern and considered the edge cases, here’s the complete code: