Problem Description

You have a regular convex polygon with n vertices labeled from 0 to n - 1 in clockwise order. Each vertex has exactly one monkey on it.

At the same moment, every monkey moves to one of its neighboring vertices (either clockwise or counterclockwise). A collision occurs when:

• Two or more monkeys end up at the same vertex after moving, OR
• Two monkeys cross paths while moving along an edge

Your task is to find the number of ways the monkeys can move such that at least one collision happens. Return the answer modulo 10^9 + 7.

Key Insights:

• Each monkey has exactly 2 choices: move clockwise or counterclockwise to a neighboring vertex
• Total possible ways for all monkeys to move = 2^n (since each of the n monkeys has 2 choices)
• The only ways to avoid ALL collisions are:
  • All monkeys move clockwise together
  • All monkeys move counterclockwise together
• These are the only 2 non-collision scenarios out of 2^n total scenarios
• Therefore, collision scenarios = 2^n - 2

The solution uses fast power to efficiently compute 2^n mod (10^9 + 7), then subtracts 2 to get the final answer.

Intuition

Let's think about when collisions DON'T happen first, as this is often easier to reason about.

Imagine all monkeys are standing on their vertices. If every monkey decides to move in the same direction (all clockwise or all counterclockwise), what happens? Each monkey moves to the position where their neighbor was standing. Since everyone moves in sync and in the same direction, no one meets on a vertex and no one crosses paths on an edge. It's like a perfect rotation of the entire configuration.

These are the ONLY two ways to avoid collisions completely. Why? Consider if even one monkey moves differently from the others:

• If monkey A moves clockwise while monkey B (its clockwise neighbor) moves counterclockwise, they'll meet on the edge between them - collision!
• If monkeys are not all moving in the same direction, there must be at least one pair of adjacent monkeys moving toward each other, causing a collision.

Now we can count:

• Total possible movements: Each of n monkeys has 2 choices (clockwise or counterclockwise), giving us 2^n total possibilities
• Non-collision movements: Only 2 ways (all clockwise or all counterclockwise)
• Collision movements: 2^n - 2

This transforms a seemingly complex collision-counting problem into a simple subtraction: total ways minus non-collision ways. The use of modular arithmetic and fast power is just an implementation detail to handle large values of n efficiently.

Learn more about Recursion and Math patterns.

Solution Approach

The implementation uses fast power (modular exponentiation) to efficiently compute 2^n mod (10^9 + 7).

Here's how the solution works:

1. Define the modulus: We set mod = 10^9 + 7 as required by the problem to prevent integer overflow for large values.

2. Calculate 2^n using fast power: The built-in Python function pow(2, n, mod) computes 2^n mod (10^9 + 7) efficiently using the fast power algorithm. This works in O(log n) time instead of O(n) time that naive multiplication would take.

3. Subtract the non-collision cases: We subtract 2 from the result to exclude the two non-collision scenarios (all monkeys moving clockwise or all counterclockwise).

4. Apply modulus again: After subtraction, we apply % mod once more to ensure the result remains within the valid range. This is important because subtracting 2 from a number that's already been reduced by modulo might give a negative result if 2^n mod (10^9 + 7) is less than 2.

The complete formula is: (pow(2, n, mod) - 2) % mod

Why fast power?

• For large values of n, computing 2^n directly would cause integer overflow
• Fast power with modular arithmetic keeps intermediate results manageable
• Time complexity: O(log n) instead of O(n)
• Space complexity: O(1)

The elegance of this solution lies in counting the complement (non-collision cases) rather than directly counting collision cases, reducing a complex combinatorial problem to a simple arithmetic operation.

Example Walkthrough

Let's walk through the solution with n = 4 (a square with 4 monkeys at vertices 0, 1, 2, 3).

Step 1: Count total possible movements

• Each monkey has 2 choices: clockwise (CW) or counterclockwise (CCW)
• Total possibilities = 2^4 = 16 ways

Step 2: Identify non-collision scenarios

• Scenario 1: All monkeys move CW
  • Monkey at 0 → 1, Monkey at 1 → 2, Monkey at 2 → 3, Monkey at 3 → 0
  • Result: Monkeys end up at different vertices, no crossings
• Scenario 2: All monkeys move CCW
  • Monkey at 0 → 3, Monkey at 1 → 0, Monkey at 2 → 1, Monkey at 3 → 2
  • Result: Monkeys end up at different vertices, no crossings
• Total non-collision ways = 2

Step 3: Identify a collision example

• Let's say: Monkeys at 0,1,2 move CW, but monkey at 3 moves CCW
• Monkey at 2 moves to vertex 3 (CW)
• Monkey at 3 moves to vertex 2 (CCW)
• These two monkeys cross paths on edge 2-3 → Collision!

Step 4: Calculate collision scenarios

• Collision ways = Total ways - Non-collision ways
• Collision ways = 16 - 2 = 14

Step 5: Apply the formula with modular arithmetic

mod = 10^9 + 7
result = (pow(2, 4, mod) - 2) % mod
result = (16 - 2) % mod
result = 14

Therefore, there are 14 ways for the monkeys to move such that at least one collision occurs.

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n)

The time complexity is determined by the pow(2, n, mod) function call. Python's built-in pow function with three arguments uses fast exponentiation (also known as binary exponentiation or exponentiation by squaring) to compute 2^n mod (10^9 + 7). This algorithm works by repeatedly squaring and reducing the exponent by half, requiring approximately log₂(n) multiplications and modulo operations. Each multiplication and modulo operation with the given modulus can be considered O(1) for practical purposes since the numbers are bounded by the modulus value. Therefore, the overall time complexity is O(log n).

Space Complexity: O(1)

The space complexity is constant because the algorithm only uses a fixed amount of extra space regardless of the input size n. The variables used are:

• mod: stores a single integer constant 10^9 + 7
• The internal space used by pow(2, n, mod) for iterative fast exponentiation is also O(1)
• The final subtraction and modulo operation use constant space

No additional data structures that scale with input size are created, making the space complexity O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting the Final Modulo Operation

The Pitfall: Many developers write pow(2, n, MOD) - 2 without the final % MOD, assuming the result is already within bounds since pow(2, n, MOD) returns a value less than MOD.

Why It's Wrong: When n = 1, we have:

• 2^1 mod (10^9 + 7) = 2
• Subtracting 2 gives us 2 - 2 = 0 ✓

But when n = 2:

• 2^2 mod (10^9 + 7) = 4
• Subtracting 2 gives us 4 - 2 = 2 ✓

However, consider edge cases where the modular result could be 0 or 1:

• If somehow 2^n mod (10^9 + 7) equals 0, then 0 - 2 = -2 (negative!)
• If somehow 2^n mod (10^9 + 7) equals 1, then 1 - 2 = -1 (negative!)

While for this specific problem with MOD = 10^9 + 7, 2^n mod MOD will never be 0, 1, or 2 for valid n values, it's still best practice to apply the final modulo to handle negative results properly.

Correct Solution:

result = (pow(2, n, MOD) - 2) % MOD

2. Using Regular Power Instead of Modular Exponentiation

The Pitfall:

# WRONG - causes overflow for large n
result = (2**n - 2) % MOD

Why It's Wrong:

• 2**n computes the full value before applying modulo
• For large n (e.g., n = 1000), 2^1000 is astronomically large and causes integer overflow in most languages
• Even in Python (which handles big integers), this is inefficient

Correct Solution:

# RIGHT - uses modular exponentiation
result = (pow(2, n, MOD) - 2) % MOD

3. Implementing Custom Fast Power Incorrectly

The Pitfall: Some developers try to implement their own fast power function but make mistakes:

def fast_power(base, exp, mod):
    result = 1
    while exp > 0:
        if exp % 2 == 1:
            result = result * base % mod  # Missing parentheses!
        base = base * base % mod
        exp //= 2
    return result

Why It's Wrong: The operator precedence issue: result * base % mod is evaluated as result * (base % mod) due to operator precedence, which can lead to overflow before the modulo is applied.

Correct Solution:

def fast_power(base, exp, mod):
    result = 1
    while exp > 0:
        if exp % 2 == 1:
            result = (result * base) % mod  # Parentheses ensure correct order
        base = (base * base) % mod
        exp //= 2
    return result

Or simply use Python's built-in pow(base, exp, mod) which handles this correctly and efficiently.