Count Collisions of Monkeys on a Polygon - Solution & Explanation
Problem Statement
There is a regular convex polygon with n vertices. The vertices are labeled from 0 to n - 1 in a clockwise direction, and each vertex has exactly one monkey. The following figure shows a convex polygon of 6 vertices.
Simultaneously, each monkey moves to a neighboring vertex. A collision happens if at least two monkeys reside on the same vertex after the movement or intersect on an edge.
Return the number of ways the monkeys can move so that at least one collision happens. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 3
Output: 6
Explanation:
There are 8 total possible movements.
Two ways such that they collide at some point are:
- Monkey 1 moves in a clockwise direction; monkey 2 moves in an anticlockwise direction; monkey 3 moves in a clockwise direction. Monkeys 1 and 2 collide.
- Monkey 1 moves in an anticlockwise direction; monkey 2 moves in an anticlockwise direction; monkey 3 moves in a clockwise direction. Monkeys 1 and 3 collide.
Example 2:
Input: n = 4
Output: 14
Constraints:
3 <= n <= 109
Approach Overview
Problem Overview: You have n monkeys sitting on the vertices of a polygon. Each monkey moves either clockwise or counterclockwise to the next vertex. A collision occurs when two monkeys land on the same vertex. The task is to count how many direction assignments lead to at least one collision.
The key observation: every monkey has two choices (clockwise or counterclockwise). That creates 2^n total movement configurations. Only two configurations avoid collisions entirely: when all monkeys move clockwise or when all move counterclockwise. Every other configuration causes at least one collision.
Approach 1: Mathematical Formula with Fast Power (Time: O(log n), Space: O(log n))
The combinatorial insight simplifies the problem dramatically. Total movement assignments equal 2^n. Exactly two arrangements avoid collisions because the entire group rotates in the same direction. Subtract those safe cases to get 2^n - 2. Since n can be large, compute the power using modular exponentiation with modulo 1e9+7. Many implementations use recursive fast power, repeatedly squaring the base while halving the exponent. This reduces the exponentiation from linear time to logarithmic time and fits naturally with recursion patterns.
Approach 2: Iterative Modular Exponentiation (Time: O(log n), Space: O(1))
This approach computes the same formula but avoids recursion. Use binary exponentiation: repeatedly square the base and multiply it into the result when the current bit of n is set. Each iteration halves the exponent using bit shifts. The result stays within bounds by applying modulo after every multiplication. The logic is straightforward and memory efficient, making it a common implementation in languages like Java or C#. This method is a classic application of math and modular arithmetic techniques used in competitive programming.
Both approaches rely on the same mathematical insight. The only difference is how 2^n is computed efficiently under modulo.
Recommended for interviews: Start by explaining the combinatorial reasoning that reduces the problem to 2^n - 2. That demonstrates strong problem modeling. Then implement fast modular exponentiation (either recursive or iterative) to compute the power in O(log n) time. Interviewers typically expect this mathematical reduction combined with efficient exponentiation.
Approach 1: Mathematical Formula
This approach involves using mathematical combinatorics. The total ways to arrange movements for n monkeys is 2^n. However, to ensure collisions, we need to exclude cases where monkeys are synchronized and move without collision. The only non-collision scenario is when all monkeys move in the same direction. Therefore, we subtract these synchronized scenarios from the total possible arrangements.
The formula to calculate the number of ways that ensure at least one collision is: 2^n - 2 (since there are 2 non-collision scenarios: all clockwise, all counterclockwise).
In this Python solution, we calculate 2^n modulo 10^9+7 to handle large numbers directly using Python's built-in pow function with three arguments, which efficiently computes (2^n) % MOD. We then subtract 2 to account for the no-collision scenarios.
Code
Python
JavaScript
C++
Complexity
Time Complexity: O(log n) due to the exponentiation by squaring technique.
Space Complexity: O(1) since the method uses constant space.
Approach 2: Iterative Modulo Exponentiation
This approach uses iterative modular exponentiation to perform efficient power calculations. Instead of directly computing 2^n, we use a loop for binary exponentiation to ensure the calculations remain accurate and efficient even for large values of n.
This Java solution utilizes binary exponentiation, where we iteratively square the base and conditionally multiply it into the result. This approach significantly reduces computation time compared to direct computation, especially for large values of n.
Complexity
Time Complexity: O(log n) because of binary exponentiation.
Space Complexity: O(1).
Approach 3: 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.
We can use fast power to calculate the value of 2^n, then use 2^n - 2 to calculate the number of collision ways of moving, and finally take the remainder of 10^9 + 7.
The time complexity is O(log n), where n is the number of monkeys. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Mathematical Formula | Time Complexity: O(log n) due to the exponentiation by squaring technique. |
| Iterative Modulo Exponentiation | Time Complexity: O(log n) because of binary exponentiation. |
| Mathematics (Fast Power) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Power Computation | O(n) | O(1) | Educational baseline when computing 2^n directly with repeated multiplication. |
| Mathematical Formula with Recursive Fast Power | O(log n) | O(log n) | Clean implementation using recursion and divide-and-conquer exponentiation. |
| Iterative Modular Exponentiation | O(log n) | O(1) | Preferred in production or interviews where constant memory and predictable control flow matter. |
Video Solution
2550. Count Collisions of Monkeys on a Polygon | Weekly Contest 330 | LeetCode 2550 • Bro Coders • 2,437 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Collisions of Monkeys on a Polygon easy or hard?
Count Collisions of Monkeys on a Polygon Python/Java solution
How to solve Count Collisions of Monkeys on a Polygon in O(log n)?
What is the best approach for Count Collisions of Monkeys on a Polygon?
Is Count Collisions of Monkeys on a Polygon asked at Google/Amazon/Meta?
What data structure is used in Count Collisions of Monkeys on a Polygon?
What is the time complexity of Count Collisions of Monkeys on a Polygon?
Ready to solve this problem?
Practice Count Collisions of Monkeys on a Polygon with our built-in code editor and test cases.
Practice on FleetCode