# Count Collisions of Monkeys on a Polygon
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-collisions-of-monkeys-on-a-polygon)
Canonical: https://scaleengineer.com/dsa/problems/count-collisions-of-monkeys-on-a-polygon
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
---
## Problem
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.

![](https://assets.glich.co/dsa/count-collisions-of-monkeys-on-a-polygon/image0.jpg) 

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.

**Example 2:**

**Input:** n = 4

**Output:** 14

**Constraints:**

* `3 <= n <= 109`

# Approaches
## Naive Iterative Power Calculation
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.
**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.
**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`).
### Explanation
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.

```java
class Solution {
    public int countCollisions(int n) {
        long M = 1_000_000_007;
        long power_of_2 = 1;
        for (int i = 0; i < n; i++) {
            power_of_2 = (power_of_2 * 2) % M;
        }
        // The result is (2^n - 2) mod M
        // We add M before taking the final modulo to handle negative results
        long result = (power_of_2 - 2 + M) % M;
        return (int) result;
    }
}
```
### Algorithm
- 1. Define the modulus `M = 10^9 + 7`.
- 2. Initialize a variable `power_of_2` to 1.
- 3. Loop from `i = 0` to `n-1`.
- 4. In each iteration, update `power_of_2 = (power_of_2 * 2) % M`.
- 5. After the loop, `power_of_2` holds the value of `2^n mod M`.
- 6. Calculate the final result as `(power_of_2 - 2 + M) % M`.
- 7. Return the result as an integer.

## Optimized Power Calculation using Binary Exponentiation
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`.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int countCollisions(int n) {
        long M = 1_000_000_007;
        long power_of_2 = power(2, n, M);
        
        // The result is (2^n - 2) mod M
        long result = (power_of_2 - 2 + M) % M;
        return (int) result;
    }

    // Helper function for binary exponentiation (exponentiation by squaring)
    private long power(long base, long exp, long mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            // If exp is odd, multiply base with res
            if (exp % 2 == 1) {
                res = (res * base) % mod;
            }
            // exp must be even now, so we can square the base 
            // and halve the exponent.
            exp >>= 1; // exp = exp / 2
            base = (base * base) % mod;
        }
        return res;
    }
}
```
### Algorithm
- 1. Identify the formula for the number of collisions: `(2^n - 2) mod M`, where `M = 10^9 + 7`.
- 2. Implement a helper function `power(base, exp, mod)` to calculate `(base^exp) mod mod` using binary exponentiation.
- 3. 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`.
- 4. Call the `power` function with `base=2`, `exp=n`, and `mod=M` to get `2^n mod M`.
- 5. Calculate the final result as `(power_of_2 - 2 + M) % M`.
- 6. Return the result.

# Solutions
### Java

```java
class Solution {
public
  int monkeyMove(int n) {
    final int mod = (int)1 e9 + 7;
    return (qpow(2, n, mod) - 2 + mod) % mod;
  }
private
  int qpow(long a, int n, int mod) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int monkeyMove(int n) {
    const int mod = 1e9 + 7;
    using ll = long long;
    auto qpow = [&](ll a, int n) {
      ll ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
      }
      return ans;
    };
    return (qpow(2, n) - 2 + mod) % mod;
  }
};

```

### Python

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

```