Count Collisions of Monkeys on a Polygon

Explore Solutions in Other Languages

Code Solution


class Solution {
 public:
  int monkeyMove(int n) {
    const int res = modPow(2, n) - 2;
    return res < 0 ? res + kMod : res;
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  long modPow(long x, long n) {
    if (n == 0)
      return 1;
    if (n % 2 == 1)
      return x * modPow(x % kMod, (n - 1)) % kMod;
    return modPow(x * x % kMod, (n / 2)) % kMod;
  }
};

Problem Description

Welcome to the whimsical world of monkeys and polygons! Imagine a bunch of monkeys, each perched on the vertices of a polygon, ready to leap into action. But wait! They’re not just jumping around aimlessly; they’re colliding with each other. The task is to count how many unique collisions occur when these monkeys decide to move.

Now, if you think about it, this is like a chaotic game of tag where everyone is trying to catch each other, but instead of running, they’re just hopping from one point to another. Picture a group of monkeys on a pentagon, and every time they jump, they might just bump into another monkey. Hilarity ensues!

Approach

The provided code uses modular exponentiation to calculate the number of unique collisions. The key idea is that each monkey can jump to two adjacent vertices, leading to a total of 2ⁿ possible movements. However, since we are interested in unique collisions, we subtract 2 (to account for the cases where no collision occurs). The result is then taken modulo 10⁹ + 7 to prevent overflow.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(log n)
Space Complexity	O(1)

Real-World Example

Imagine a group of monkeys at a party, each standing at the corners of a dance floor shaped like a polygon. As the music plays, they decide to dance towards their neighbors. Sometimes they bump into each other, and sometimes they don’t. The goal is to figure out how many times they collide while trying to show off their best moves. Just like in our code, we want to count those unique dance collisions without getting lost in the chaos!