LeetCode 2550 - Count Collisions of Monkeys on a Polygon

In this problem, we have a regular polygon with n vertices, and each vertex initially contains exactly one monkey. Every monkey must move simultaneously to one of its two neighboring vertices.

leetcodemediummathrecursion

LeetCode Problem 2550

Difficulty: 🟡 Medium
Topics: Math, Recursion

Solution

Problem Understanding

In this problem, we have a regular polygon with n vertices, and each vertex initially contains exactly one monkey. Every monkey must move simultaneously to one of its two neighboring vertices. Since each monkey has only two choices, clockwise or counterclockwise, the total number of possible movement configurations is 2^n.

A collision occurs in two situations. The first situation is when two or more monkeys end up on the same vertex after moving. The second situation is when two monkeys move across the same edge in opposite directions and cross each other in the middle of the edge.

The task is to count how many movement configurations produce at least one collision. Because the answer can become extremely large, we return the result modulo 10^9 + 7.

The input consists of a single integer n, representing the number of vertices in the polygon. The output is a single integer, the number of movement patterns that produce at least one collision.

The constraint 3 <= n <= 10^9 is extremely important. Since n can be as large as one billion, any algorithm that iterates through all possible movement patterns is impossible. Even linear time solutions would be too slow if they required explicitly simulating all movements. This strongly suggests that the solution must rely on mathematical reasoning and fast exponentiation.

One important observation is that every monkey always moves exactly one step. Therefore, the only way to avoid collisions entirely is if all monkeys move in the same direction. If even one monkey moves differently from its neighbor, a collision becomes unavoidable.

Another important edge case is very large values of n. Since 2^n grows astronomically fast, modular arithmetic must be applied during exponentiation to avoid overflow.

Approaches

Brute Force Approach

A brute force solution would generate every possible movement configuration. Since each monkey has two choices, there are 2^n total configurations.

For each configuration, we could simulate the movement of all monkeys and check whether any collision occurs. We would need to track destination vertices and also detect edge crossings between adjacent monkeys moving in opposite directions.

This approach is correct because it explicitly evaluates every possible movement pattern and directly verifies whether a collision occurs.

However, the complexity is completely impractical. With n = 10^9, even storing all configurations is impossible. The exponential growth makes brute force infeasible for anything beyond very small values of n.

Optimal Mathematical Observation

The key insight is that there are only two ways to avoid collisions entirely:

  1. Every monkey moves clockwise.
  2. Every monkey moves counterclockwise.

In both of these cases, each monkey moves to a unique adjacent vertex, and no two monkeys cross paths.

Now consider any mixed movement pattern. Suppose one monkey moves clockwise while an adjacent monkey moves counterclockwise. They must cross each other along their shared edge, creating a collision immediately.

Therefore:

  • Total movement patterns = 2^n
  • Collision free patterns = 2
  • Collision patterns = 2^n - 2

The remaining challenge is efficiently computing 2^n mod (10^9 + 7) for very large n. This is done using fast modular exponentiation, also called binary exponentiation.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × 2^n) O(n) Enumerates every movement configuration
Optimal O(log n) O(1) Uses mathematical observation and fast exponentiation

Algorithm Walkthrough

  1. Define the modulus value as 10^9 + 7.

This modulus is required because the result can become extremely large. All computations must remain within modular arithmetic limits. 2. Compute 2^n mod MOD.

Since n can be as large as 10^9, directly computing 2^n is impossible. Instead, use binary exponentiation, which repeatedly squares the base and processes one bit of the exponent at a time. 3. Subtract the two collision free configurations.

The only collision free arrangements are:

  • All monkeys move clockwise
  • All monkeys move counterclockwise

Therefore, the answer is:

$2^n - 2$ 4. Ensure the result remains nonnegative.

In modular arithmetic, subtraction can produce a negative intermediate value. Add MOD before taking the final modulo operation. 5. Return the final result.

Why it works

Every monkey moves to one of two neighboring vertices. If all monkeys move in the same direction, each monkey shifts uniformly around the polygon, so no collisions occur.

Now suppose at least one monkey moves differently from one of its adjacent monkeys. Along the edge connecting them, one monkey travels clockwise while the other travels counterclockwise. Their paths intersect on that edge, guaranteeing a collision.

Thus, exactly two configurations avoid collisions, and all remaining 2^n - 2 configurations produce at least one collision.

Python Solution

class Solution:
    def monkeyMove(self, n: int) -> int:
        MOD = 10**9 + 7
        
        total_ways = pow(2, n, MOD)
        
        return (total_ways - 2 + MOD) % MOD

The implementation is extremely compact because Python already provides an efficient modular exponentiation function through pow(base, exponent, mod).

The variable MOD stores the required modulus. The expression pow(2, n, MOD) computes 2^n mod MOD using binary exponentiation internally, which runs in logarithmic time.

After computing the total number of movement patterns, we subtract the two collision free cases. The expression (total_ways - 2 + MOD) % MOD guarantees the result remains nonnegative under modular arithmetic.

Go Solution

func monkeyMove(n int) int {
    const MOD int64 = 1_000_000_007

    power := modPow(2, int64(n), MOD)

    return int((power - 2 + MOD) % MOD)
}

func modPow(base, exponent, mod int64) int64 {
    result := int64(1)

    base %= mod

    for exponent > 0 {
        if exponent%2 == 1 {
            result = (result * base) % mod
        }

        base = (base * base) % mod
        exponent /= 2
    }

    return result
}

The Go version explicitly implements binary exponentiation because Go does not provide a built in modular power function equivalent to Python's pow.

The helper function modPow repeatedly squares the base and processes the exponent bit by bit. Using int64 is important because intermediate multiplication results can exceed the range of standard 32 bit integers.

The final subtraction uses (power - 2 + MOD) % MOD to avoid negative values after subtraction.

Worked Examples

Example 1

Input:

n = 3

Total movement patterns:

$2^3 = 8$

Collision free patterns:

Pattern Collision
Clockwise, Clockwise, Clockwise No
Counterclockwise, Counterclockwise, Counterclockwise No

All other patterns produce collisions.

Final calculation:

Step Value
Total patterns 8
Collision free 2
Collision patterns 8 - 2 = 6

Output:

6

Example 2

Input:

n = 4

Total movement patterns:

$2^4 = 16$

Collision free patterns:

Pattern Collision
All clockwise No
All counterclockwise No

All remaining patterns produce collisions.

Final calculation:

Step Value
Total patterns 16
Collision free 2
Collision patterns 16 - 2 = 14

Output:

14

Complexity Analysis

Measure Complexity Explanation
Time O(log n) Binary exponentiation processes each bit of the exponent
Space O(1) Only constant extra variables are used

The algorithm is dominated by modular exponentiation. Binary exponentiation repeatedly halves the exponent, so the number of iterations is proportional to the number of bits in n, which is O(log n).

The space usage remains constant because no additional data structures proportional to input size are allocated.

Test Cases

sol = Solution()

assert sol.monkeyMove(3) == 6          # Example case
assert sol.monkeyMove(4) == 14         # Example case
assert sol.monkeyMove(5) == 30         # 2^5 - 2
assert sol.monkeyMove(6) == 62         # 2^6 - 2
assert sol.monkeyMove(10) == 1022      # Larger small value

assert sol.monkeyMove(500000003) >= 0  # Very large n
assert sol.monkeyMove(10**9) >= 0      # Maximum constraint stress test

MOD = 10**9 + 7
assert sol.monkeyMove(3) == (pow(2, 3, MOD) - 2) % MOD
assert sol.monkeyMove(100) == (pow(2, 100, MOD) - 2) % MOD
Test Why
n = 3 Smallest example from the statement
n = 4 Verifies another provided example
n = 5 Checks normal behavior for odd polygon size
n = 6 Checks normal behavior for even polygon size
n = 10 Verifies correctness on larger values
n = 500000003 Tests logarithmic scalability
n = 10^9 Maximum constraint stress test
Formula validation tests Confirms implementation matches mathematical derivation

Edge Cases

One important edge case is the minimum valid input, n = 3. Small polygons are often sources of logical mistakes because adjacency wraps around immediately. The implementation handles this naturally because the formula 2^n - 2 remains valid even for the smallest polygon.

Another important edge case is extremely large values such as n = 10^9. A naive implementation that computes 2^n directly would overflow or run indefinitely. Using modular binary exponentiation ensures the computation finishes efficiently in logarithmic time.

A third important edge case involves modular subtraction. If the expression 2^n mod MOD happens to be smaller than 2, directly subtracting could produce a negative result. The implementation avoids this issue with:

(total_ways - 2 + MOD) % MOD

This guarantees the final answer remains within the valid modular range.