Count Collisions of Monkeys on a Polygon

Count Collisions of Monkeys on a Polygon

What is this problem about?

In the Count Collisions of Monkeys on a Polygon interview question, n monkeys are placed on the n vertices of a convex polygon. Each monkey can move to an adjacent vertex (clockwise or counter-clockwise). You need to find the number of ways the monkeys can move such that at least one collision occurs. A collision happens if two monkeys move towards each other on the same edge or end up on the same vertex. Return the answer modulo 10^9 + 7.

Why is this asked in interviews?

Goldman Sachs and Amazon ask the Count Collisions of Monkeys on a Polygon coding problem to test your knowledge of combinatorics and modular exponentiation. It’s a "Medium" problem that requires a "Complementary Counting" approach—it's much easier to count the cases where no collisions occur.

Algorithmic pattern used

This is a Math / Combinatorics problem.

1. Each of the n monkeys has 2 choices (Clockwise or Counter-clockwise). Total ways to move = 2^n.
2. A collision does not occur only in two specific scenarios:
   • All monkeys move Clockwise.
   • All monkeys move Counter-clockwise.
3. Number of collision-free ways = 2.
4. Total ways with collisions = (2^n - 2) % (10^9 + 7).
5. Use Binary Exponentiation to calculate 2^n in O(log N) time.

Example explanation

n = 3 (Triangle)

1. Total ways = 2^3 = 8.
2. Collision-free: [CW, CW, CW] and [CCW, CCW, CCW].
3. Total collisions = 8 - 2 = 6. Result: 6.

Common mistakes candidates make

• Negative Results: When calculating (total - 2) % mod, the result can be negative in languages like Java or C++. Always use (total - 2 + mod) % mod.
• Linear Power: Using a loop to calculate 2^n, which takes O(N) and will time out for n = 10^9.
• Logic Error: Thinking there are more collision-free cases than just the two circular rotations.

Interview preparation tip

"Complementary counting" is a standard interview strategy. If a problem asks for "at least one," try calculating the case for "none" and subtracting it from the total.