Count collisions of monkeys on a polygon

Math Recursion

30.0% acceptance

Feb 25, 2026

268

531

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn monkey_move(n: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    // Total ways = 2^n, non-collision = 2 (all clockwise or all counter-clockwise)
    // Answer = 2^n - 2 mod MOD
    let mut result = 1i64;
    let mut base = 2i64;
    let mut exp = n as u64;
    while exp > 0 {
      if exp & 1 == 1 {
        result = result * base % MOD;
      }
      base = base * base % MOD;
      exp >>= 1;
    }
    ((result - 2 + MOD) % MOD) as i32
  }
}