Count Collisions of Monkeys on a Polygon — Solution
Count Collisions of Monkeys on a Polygon solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count Collisions of Monkeys on a Polygon is a medium coding problem on math and recursion, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Math, Recursion
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A regular polygon has n vertices numbered 0 to n - 1 clockwise, and one monkey sits on every vertex. At the same moment every monkey moves to one of its two neighbouring vertices — clockwise or anticlockwise.
A collision happens if, after the move, two monkeys share a vertex, or if two monkeys cross each other on an edge.
Return the number of ways the monkeys can move so that at least one collision happens, modulo 10^9 + 7.
Example 1
Input: n = 3
Output: 6
Explanation: There are 2³ = 8 ways to move; only 'all clockwise' and 'all anticlockwise' avoid a collision.
Example 2
Input: n = 4
Output: 14
Example 3
Input: n = 1000000000
Output: 140624999
Constraints
3 <= n <= 10^9
Hints for Count Collisions of Monkeys on a Polygon
Hint 1
Count the complement: in how many ways can the monkeys move with no collision at all?
Hint 2
If one monkey goes clockwise and its clockwise neighbour goes anticlockwise, they cross on the edge between them. What does that force around the polygon?
Hint 3
Only 'everyone clockwise' and 'everyone anticlockwise' are collision-free, so the answer is
2^n - 2— compute the power by repeated squaring.
How to solve Count Collisions of Monkeys on a Polygon
Every monkey has two choices, 2^n ways in total, and exactly two of them — all clockwise or all anticlockwise — avoid every collision. The answer is (2^n - 2) mod (10^9 + 7).
Approach
- Compute
2^n mod Mwith binary exponentiation (M = 10^9 + 7). - Subtract 2 and add
Mbefore reducing again, so the result never goes negative.
Why it works
If all monkeys move the same way, the configuration just rotates: no vertex is shared and no two monkeys use the same edge. Otherwise, going around the polygon there is some monkey moving clockwise whose clockwise neighbour moves anticlockwise; they swap along their shared edge and collide. So the collision-free moves are exactly the two uniform ones, and all other 2^n - 2 moves contain a collision.
Complexity
- Time —
O(log n) - Space —
O(1)
Pitfalls
2^n mod Mcan be 0 or 1, so2^n mod M - 2can be negative — addMbefore taking the modulus again.- n reaches 10^9: a loop that doubles n times is too slow; use repeated squaring.
- Multiply two residues in 64 bits (or split the multiplication in JavaScript).
Reference solution
Python
def monkeyMove(n: int) -> int:
MOD = 10 ** 9 + 7
return (pow(2, n, MOD) - 2) % MODJava
public static int monkeyMove(int n) {
final long MOD = 1000000007L;
long r = 1, b = 2;
int e = n;
while (e > 0) {
if ((e & 1) == 1) r = r * b % MOD;
b = b * b % MOD;
e >>= 1;
}
return (int) ((r - 2 + MOD) % MOD);
}C++
int monkeyMove(int n) {
const long long MOD = 1000000007LL;
long long r = 1, b = 2;
int e = n;
while (e > 0) {
if (e & 1) r = r * b % MOD;
b = b * b % MOD;
e >>= 1;
}
return (int) ((r - 2 + MOD) % MOD);
}JavaScript
var monkeyMove = function(n) {
var MOD = 1000000007;
var mulMod = function(a, b) {
var hi = Math.floor(b / 65536), lo = b % 65536;
return ((a * hi) % MOD * 65536 + a * lo) % MOD;
};
var r = 1, b = 2, e = n;
while (e > 0) {
if (e % 2 === 1) r = mulMod(r, b);
b = mulMod(b, b);
e = Math.floor(e / 2);
}
return (r - 2 + MOD) % MOD;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Recursion