#2550

Medium

LeetCode Problem Workspace

Count Collisions of Monkeys on a Polygon

Calculate the total number of monkey collisions on a convex polygon using math and recursion efficiently for large n.

Problem Statement

Given a regular convex polygon with n vertices labeled 0 to n-1 clockwise, each vertex holds one monkey. All monkeys move simultaneously to an adjacent vertex. Count all configurations where at least two monkeys collide at a vertex or along an edge.

Return the total number of movement patterns leading to at least one collision. Since the number can be very large, return the result modulo 10^9 + 7. Ensure your solution handles large n efficiently, applying recursion and mathematical counting for optimization.

Examples

Example 1

Input: n = 3

Output: 6

There are 8 total possible movements. Two ways such that they collide at some point are:

Example 2

Input: n = 4

Output: 14

Example details omitted.

Constraints

3 <= n <= 109

Solution Approach

Count total possible movements

Each monkey has exactly two movement options, so there are 2^n total movement combinations. This represents all configurations regardless of collisions.

Calculate non-collision scenarios recursively

Define a recurrence to count sequences where no collisions occur. Use the polygon's adjacency to propagate valid moves, ensuring no two monkeys occupy the same vertex or edge after moving.

Subtract non-collision from total and apply modulo

The total collision count is total movements minus non-collision movements. Return the result modulo 10^9 + 7. Recursion helps manage overlapping subproblems without enumerating all possibilities.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on the recursive method used. Direct enumeration is exponential, but dynamic programming or combinatorial formulas reduce it to O(n) space and O(n) time.

What Interviewers Usually Probe

Emphasizes counting with recursion and modular arithmetic.
Checks if candidate recognizes collisions on edges as well as vertices.
Wants efficient handling for very large n using math patterns.

Common Pitfalls or Variants

Common pitfalls

Forgetting edge collisions between monkeys.
Attempting to enumerate all 2^n configurations for large n.
Incorrect modulo operations causing overflow.

Follow-up variants

Compute collisions on a circular track instead of polygon vertices.
Count configurations where exactly k collisions occur.
Handle polygons with some fixed vertices blocked.

FAQ

What is the key pattern in Count Collisions of Monkeys on a Polygon?

The key pattern is using recursion combined with combinatorial math to count non-collision sequences, then subtracting from total movements.

How do you handle very large n efficiently?

Use recursion with memoization or combinatorial formulas instead of enumerating all 2^n possibilities, applying modulo 10^9 + 7.

Do collisions along edges count?

Yes, a collision occurs if monkeys intersect on the same edge while moving to adjacent vertices.

Can this approach be adapted to a circular track?

Yes, the same recursion and counting logic applies to circular arrangements, adjusting adjacency accordingly.

Why subtract non-collision configurations from total?

Counting non-collision movements allows us to efficiently find all collision scenarios without enumerating every configuration.

terminal

Solution

Solution 1: Mathematics (Fast Power)

According to the problem description, each monkey has two ways of moving, either clockwise or counterclockwise. Therefore, there are a total of $2^n$ ways to move. The non-collision ways of moving are only two, that is, all monkeys move clockwise or all monkeys move counterclockwise. Therefore, the number of collision ways of moving is $2^n - 2$.

1

2

3

4

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

Continue Practicing

#1969 minimum non zero product of the array elements #1922 count good numbers #1823 find the winner of the circular game