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.

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`.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

1
2
3
4


Input: n = 4

Output: 14

Constraints

  • 3 <= n <= 10^9

Solution

Method 1 – Inclusion-Exclusion Principle & Modular Exponentiation

Intuition

Each monkey can move either clockwise or counterclockwise, so there are 2^n total ways. However, if all monkeys move in the same direction, there are no collisions (since they all rotate together). So, we subtract these 2 cases (all clockwise or all counterclockwise) from the total. The answer is (2^n - 2) modulo 1e9+7.

Approach

  1. Calculate the total number of ways: 2^n.
  2. Subtract the 2 cases where all monkeys move in the same direction.
  3. Return the result modulo 1e9+7.
  4. Use fast modular exponentiation for efficiency, since n can be up to 10^9.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int monkeyMove(int n) {
        const int mod = 1e9 + 7;
        long long ans = 1;
        long long base = 2;
        int exp = n;
        while (exp) {
            if (exp & 1) ans = (ans * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        ans = (ans - 2 + mod) % mod;
        return (int)ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func monkeyMove(n int) int {
    mod := int(1e9 + 7)
    ans := 1
    base := 2
    exp := n
    for exp > 0 {
        if exp&1 == 1 {
            ans = ans * base % mod
        }
        base = base * base % mod
        exp >>= 1
    }
    ans = (ans - 2 + mod) % mod
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int monkeyMove(int n) {
        int mod = 1_000_000_007;
        long ans = 1, base = 2;
        int exp = n;
        while (exp > 0) {
            if ((exp & 1) == 1) ans = (ans * base) % mod;
            base = (base * base) % mod;
            exp >>= 1;
        }
        ans = (ans - 2 + mod) % mod;
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun monkeyMove(n: Int): Int {
        val mod = 1_000_000_007
        var ans = 1L
        var base = 2L
        var exp = n
        while (exp > 0) {
            if (exp and 1 == 1) ans = ans * base % mod
            base = base * base % mod
            exp = exp shr 1
        }
        ans = (ans - 2 + mod) % mod
        return ans.toInt()
    }
}
1
2
3
4
5

class Solution:
    def monkeyMove(self, n: int) -> int:
        mod = 10**9 + 7
        ans = pow(2, n, mod)
        return (ans - 2) % mod
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn monkey_move(n: i32) -> i32 {
        let m = 1_000_000_007;
        let mut ans = 1i64;
        let mut base = 2i64;
        let mut exp = n as i64;
        while exp > 0 {
            if exp & 1 == 1 {
                ans = ans * base % m;
            }
            base = base * base % m;
            exp >>= 1;
        }
        ((ans - 2 + m) % m) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    monkeyMove(n: number): number {
        const mod = 1e9 + 7;
        let ans = 1n;
        let base = 2n;
        let exp = BigInt(n);
        while (exp > 0n) {
            if (exp & 1n) ans = ans * base % BigInt(mod);
            base = base * base % BigInt(mod);
            exp >>= 1n;
        }
        return Number((ans - 2n + BigInt(mod)) % BigInt(mod));
    }
}

Complexity

  • ⏰ Time complexity: O(log n), because modular exponentiation is logarithmic in n.
  • 🧺 Space complexity: O(1), only a constant amount of space is used.