LeetCode 2550: Count Collisions of Monkeys on a Polygon Solution
Master LeetCode problem 2550 (Count Collisions of Monkeys on a Polygon), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
Problem Explanation
Explanation
To solve this problem, we can realize that the monkeys on a polygon of n vertices will collide if and only if there is at least one vertex with more than one monkey after the movement. We need to count the number of ways the monkeys can move so that at least one collision happens.
We can approach this problem by considering the cases where no collisions happen. If we can count these cases, we can subtract them from the total possible movements to get the number of ways for at least one collision to occur.
To count the cases where no collisions happen, we need to consider the permutations of monkeys such that each monkey is at a different vertex after the movement. This can be calculated using the formula for derangements (permutations without fixed points), which is given by !n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n * 1/n!).
The final answer is then the total possible movements (n^n) minus the number of ways where no collisions happen.
- Time complexity: O(n)
- Space complexity: O(1)
Solution Code
class Solution {
public int countCollisions(int n) {
long MOD = 1000000007;
long result = 1;
for (int i = 1; i <= n; i++) {
result = (result * i) % MOD;
}
long derangement = 1;
for (int i = 0; i <= n; i++) {
derangement = (derangement + ((i % 2 == 0) ? 1 : -1) * modInverse(i, MOD)) % MOD;
}
return (int) ((result - derangement + MOD) % MOD);
}
private long modInverse(int x, long MOD) {
if (x == 0) return 1;
long result = 1;
for (int i = 1; i <= x; i++) {
result = (result * i) % MOD;
}
return pow(result, MOD - 2, MOD);
}
private long pow(long x, long y, long MOD) {
long result = 1;
while (y > 0) {
if (y % 2 == 1) {
result = (result * x) % MOD;
}
x = (x * x) % MOD;
y /= 2;
}
return result;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 2550 (Count Collisions of Monkeys on a Polygon)?
This page provides optimized solutions for LeetCode problem 2550 (Count Collisions of Monkeys on a Polygon) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 2550 (Count Collisions of Monkeys on a Polygon)?
The time complexity for LeetCode 2550 (Count Collisions of Monkeys on a Polygon) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 2550 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2550 in Java, C++, or Python.