2550. Count Collisions of Monkeys on a Polygon LeetCode Solution

In this guide, you will get 2550. Count Collisions of Monkeys on a Polygon LeetCode Solution with the best time and space complexity. The solution to Count Collisions of Monkeys on a Polygon problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Count Collisions of Monkeys on a Polygon solution in C++
  4. Count Collisions of Monkeys on a Polygon solution in Java
  5. Count Collisions of Monkeys on a Polygon solution in Python
  6. Additional Resources
2550. Count Collisions of Monkeys on a Polygon LeetCode Solution image

Problem Statement of Count Collisions of Monkeys on a Polygon

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.

See also  2455. Average Value of Even Numbers That Are Divisible by Three LeetCode Solution

Example 2:

Input: n = 4
Output: 14

Constraints:

3 <= n <= 109

Complexity Analysis

  • Time Complexity: O(\log n)
  • Space Complexity: O(\log n)

2550. Count Collisions of Monkeys on a Polygon LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

2550. Count Collisions of Monkeys on a Polygon LeetCode Solution in Java

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

  private static final int kMod = 1_000_000_007;

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

2550. Count Collisions of Monkeys on a Polygon LeetCode Solution in Python

class Solution:
  def monkeyMove(self, n: int) -> int:
    kMod = 1_000_000_007
    res = pow(2, n, kMod) - 2
    return res + kMod if res < 0 else res
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: