Watch 10 video solutions for Count Collisions of Monkeys on a Polygon, a medium level problem involving Math, Recursion. This walkthrough by Bro Coders has 2,411 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
Example 2:
Input: n = 4
Output: 14
Constraints:
3 <= n <= 109Problem 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 | 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. |