Count Collisions of Monkeys on a Polygon solution and explanation
9 more videos on this problem
2550. Count Collisions of Monkeys on a Polygon | Weekly Contest 330 | LeetCode 2550Bro Coders · 6:55 · 2K views
Count Collisions of Monkeys on a Polygon || Weekly Contest 330 || C++ || MediumPriyanshi Porwal · 8:05 · 1K views
2550. Count Collisions of Monkeys on a Polygon (Leetcode Medium)Programming Live with Larry · 3:35 · 725 views
2550. Count Collisions of Monkeys on a Polygon | Leetcode contest 330Tech Courses · 5:33 · 540 views
Count Collisions of Monkeys on a Polygon| #6338 | Leetcode | JAVA ✅ | 🔥Vishwas aithal · 1:33 · 448 views
[Beats 100% Solution] 2550. Count Collisions of Monkeys on a PolygonTheGrayMind · 4:51 · 358 views
Leetcode 2550. Count Collisions of Monkeys on a PolygonAlgorithms Casts · 9:36 · 317 views
2550. Count Collisions of Monkeys on a Polygon|| Hindi (हिन्दी)|| Weekly contest 330 29January 2023CodeVed | Sanjib Asiwal · 5:46 · 290 views
Leetcode 2550 | Count Collisions of Monkeys on a Polygon | weekly contest 330 | mediumCoding Together · 5:27 · 277 views
B. Count Collision of Monkey on a Polygon - LEETCODE WEEKLY CONTEST 330 (Code + Explanation)Joyjit Codes · 3:45 · 2K views
The problem
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).
def collision_count(n):
MOD = 10**9 + 7
return (pow(2, n, MOD) - 2) % MOD#include <iostream>
#include <cmath>
using namespace std;
#define MOD 1000000007
long long collisionCount(int n) {
return (static_cast<long long>(pow(2, n)) - 2 + MOD) % MOD;
}function collisionCount(n) {
const MOD = 1e9 + 7;
return (Math.pow(2, n) - 2 + MOD) % MOD;
}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.
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.
public class Solution {
public int collisionCount(int n) {
int MOD = 1000000007;
long result = 1, base = 2;
while (n > 0) {
if ((n & 1) == 1) result = result * base % MOD;
base = base * base % MOD;
n >>= 1;
}
return (int)((result - 2 + MOD) % MOD);
}
}public class Solution {
public int CollisionCount(int n) {
const int MOD = 1000000007;
long result = 1, base = 2;
while (n > 0) {
if ((n & 1) == 1) result = result * base % MOD;
base = base * base % MOD;
n >>= 1;
}
return (int)((result - 2 + MOD) % MOD);
}
}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.
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).
function monkeyMove(n: number): number {
const mod = 10 ** 9 + 7;
const qpow = (a: number, n: number): number => {
let ans = 1n;
for (; n; n >>>= 1) {
if (n & 1) {
ans = (ans * BigInt(a)) % BigInt(mod);
}
a = Number((BigInt(a) * BigInt(a)) % BigInt(mod));
}
return Number(ans);
};
return (qpow(2, n) - 2 + mod) % mod;
}func monkeyMove(n int) int {
const mod = 1e9 + 7
qpow := func(a, n int) int {
ans := 1
for ; n > 0; n >>= 1 {
if n&1 == 1 {
ans = ans * a % mod
}
a = a * a % mod
}
return ans
}
return (qpow(2, n) - 2 + mod) % mod
}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) | – |
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. |
Frequently asked questions
Is Count Collisions of Monkeys on a Polygon easy or hard?
The problem is rated Medium because the implementation is simple once you discover the mathematical insight. The challenge is recognizing that only two direction assignments avoid collisions, reducing the problem to computing 2^n - 2 efficiently.
Count Collisions of Monkeys on a Polygon Python/Java solution
The implementation computes (2^n - 2) mod 1e9+7 using fast exponentiation. Python often uses pow(2, n, MOD) for built-in modular power, while Java implementations typically implement iterative binary exponentiation to avoid overflow.
How to solve Count Collisions of Monkeys on a Polygon in O(log n)?
First derive the formula: total configurations are 2^n and exactly two produce no collisions. The answer is (2^n - 2) mod 1e9+7. Use fast exponentiation (binary exponentiation) to compute 2^n under modulo in O(log n) time.
What is the best approach for Count Collisions of Monkeys on a Polygon?
The optimal approach uses a mathematical observation: there are 2^n possible movement combinations and only two avoid collisions (all clockwise or all counterclockwise). Subtract those from the total to get 2^n - 2. Compute 2^n using fast modular exponentiation in O(log n) time to handle large inputs.
Is Count Collisions of Monkeys on a Polygon asked at Google/Amazon/Meta?
Problems like this appear in interviews that test mathematical modeling and modular arithmetic, commonly seen in companies such as Google, Amazon, and fintech or quant-heavy teams. The focus is recognizing the combinatorial pattern rather than simulation.
What data structure is used in Count Collisions of Monkeys on a Polygon?
No complex data structure is required. The solution relies purely on mathematical reasoning and modular exponentiation, sometimes implemented with recursion or iterative binary exponentiation.
What is the time complexity of Count Collisions of Monkeys on a Polygon?
The optimal solution runs in O(log n) time because it computes 2^n using binary (fast) exponentiation. Each step halves the exponent, drastically reducing the number of multiplications compared to a naive O(n) approach.