Count Collisions of Monkeys on a Polygon

Med

#2330Time: O(n). The loop runs `n` times to calculate the power, which is too slow for the given constraints.Space: O(1). We only use a few variables to store the intermediate results.

Patterns

Math Recursion

Prompt

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 10⁹+ 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.

Example 2:

Input: n = 4

Output: 14

Constraints:

3 <= n <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first identifies the core mathematical formula for the problem: (Total Ways - Non-Collision Ways). The total number of ways is 2^n since each of the n monkeys has 2 choices. Non-collision ways occur only when all monkeys move in the same direction (all clockwise or all counter-clockwise), which accounts for 2 ways. Thus, the number of ways with at least one collision is 2^n - 2. This approach then calculates 2^n using a simple loop, taking the modulo 10^9 + 7 at each step to prevent overflow.

Algorithm

1. Define the modulus M = 10^9 + 7.
1. Initialize a variable power_of_2 to 1.
1. Loop from i = 0 to n-1.
1. In each iteration, update power_of_2 = (power_of_2 * 2) % M.
1. After the loop, power_of_2 holds the value of 2^n mod M.
1. Calculate the final result as (power_of_2 - 2 + M) % M.
1. Return the result as an integer.

Walkthrough

The problem can be simplified by calculating the total number of possible movements and subtracting the number of movements that result in no collisions.

Each of the n monkeys can move to one of two adjacent vertices (clockwise or counter-clockwise). Therefore, the total number of possible movement combinations is 2 * 2 * ... * 2 (n times), which equals 2^n.
A collision is avoided only if all monkeys move in unison, maintaining their relative positions. This happens in two scenarios:
1. All monkeys move one step clockwise.
2. All monkeys move one step counter-clockwise.
So, there are only 2 non-colliding scenarios.
The number of ways with at least one collision is (Total ways) - (Non-colliding ways) = 2^n - 2.
To compute 2^n mod M (where M = 10^9 + 7), this approach uses a simple for-loop that iterates n times.
We initialize a variable power_of_2 to 1. In each iteration, we multiply it by 2 and take the modulo M.
After the loop, we subtract 2 from the result and take the modulo again to get the final answer. Note that we add M before the final modulo operation to handle potential negative results if power_of_2 is less than 2.

1class Solution {2    public int countCollisions(int n) {3        long M = 1_000_000_007;4        long power_of_2 = 1;5        for (int i = 0; i < n; i++) {6            power_of_2 = (power_of_2 * 2) % M;7        }8        // The result is (2^n - 2) mod M9        // We add M before taking the final modulo to handle negative results10        long result = (power_of_2 - 2 + M) % M;11        return (int) result;12    }13}

Complexity

Time

O(n). The loop runs `n` times to calculate the power, which is too slow for the given constraints.

Space

O(1). We only use a few variables to store the intermediate results.

Trade-offs

Pros

Simple to understand and implement.
Correctly identifies the mathematical formula.

Cons

The time complexity is linear in n.
It will result in a "Time Limit Exceeded" (TLE) error for large values of n (up to 10^9).

This approach uses the same mathematical formula as the naive approach: (2^n - 2) mod M. However, it calculates 2^n mod M much more efficiently using a technique called Binary Exponentiation (or Exponentiation by Squaring). This algorithm computes powers in logarithmic time, which is necessary to pass the time constraints given n can be as large as 10^9.

Algorithm

1. Identify the formula for the number of collisions: (2^n - 2) mod M, where M = 10^9 + 7.
1. Implement a helper function power(base, exp, mod) to calculate (base^exp) mod mod using binary exponentiation.
1. Inside the power function:
- a. Initialize res = 1.
- b. Loop while exp > 0.
- c. If exp is odd, update res = (res * base) % mod.
- d. Update base = (base * base) % mod.
- e. Update exp = exp / 2.
- f. Return res.
1. Call the power function with base=2, exp=n, and mod=M to get 2^n mod M.
1. Calculate the final result as (power_of_2 - 2 + M) % M.
1. Return the result.

Walkthrough

The core idea is to find (2^n - 2) mod M. The bottleneck is calculating 2^n mod M for a very large n.

Binary Exponentiation is an efficient algorithm for this. It works by repeatedly squaring the base and using the binary representation of the exponent.

The principle is:

If the exponent n is even, a^n = (a^2)^(n/2).
If the exponent n is odd, a^n = a * a^(n-1) = a * (a^2)^((n-1)/2).

This allows us to reduce the problem size by half in each step, leading to a logarithmic time complexity. We can implement this iteratively. We initialize result = 1 and base = 2. We iterate while n > 0.

If the current last bit of n is 1 (i.e., n % 2 == 1), we multiply our result by the current base.
Then, we square the base (base = base * base) and right-shift n by one (n = n / 2).
All multiplications are performed under the modulus M.
After computing 2^n mod M, we subtract 2 and take the final modulo to get the answer.

1class Solution {2    public int countCollisions(int n) {3        long M = 1_000_000_007;4        long power_of_2 = power(2, n, M);5        6        // The result is (2^n - 2) mod M7        long result = (power_of_2 - 2 + M) % M;8        return (int) result;9    }10 11    // Helper function for binary exponentiation (exponentiation by squaring)12    private long power(long base, long exp, long mod) {13        long res = 1;14        base %= mod;15        while (exp > 0) {16            // If exp is odd, multiply base with res17            if (exp % 2 == 1) {18                res = (res * base) % mod;19            }20            // exp must be even now, so we can square the base 21            // and halve the exponent.22            exp >>= 1; // exp = exp / 223            base = (base * base) % mod;24        }25        return res;26    }27}

Complexity

Time

O(log n). The number of iterations in the binary exponentiation algorithm is proportional to the number of bits in `n`, which is `log2(n)`.

Space

O(1) for the iterative implementation. A recursive implementation would use O(log n) stack space.

Trade-offs

Pros

Extremely efficient, with logarithmic time complexity.
Easily handles the large constraint on n.
It's a standard and widely applicable algorithm for modular arithmetic.

Cons

The logic for binary exponentiation is slightly more complex than a simple loop.

Solutions

Solution

1class Solution {2public3  int monkeyMove(int n) {4    final int mod = (int)1 e9 + 7;5    return (qpow(2, n, mod) - 2 + mod) % mod;6  }7private8  int qpow(long a, int n, int mod) {9    long ans = 1;10    for (; n > 0; n >>= 1) {11      if ((n & 1) == 1) {12        ans = ans * a % mod;13      }14      a = a * a % mod;15    }16    return (int)ans;17  }18}

1class Solution {2public:3  int monkeyMove(int n) {4    const int mod = 1e9 + 7;5    using ll = long long;6    auto qpow = [&](ll a, int n) {7      ll ans = 1;8      for (; n; n >>= 1) {9        if (n & 1) {10          ans = ans * a % mod;11        }12        a = a * a % mod;13      }14      return ans;15    };16    return (qpow(2, n) - 2 + mod) % mod;17  }18};

1class Solution:2    def monkeyMove(self, n: int) -> int: mod = 10 ** 9 + 7 return (pow(2, n, mod) - 2) % mod

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem