Count Collisions of Monkeys on a Polygon - Practice Coding Problems

Count Collisions of Monkeys on a Polygon - Problem

Math Recursion Medium

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.

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.

Input & Output

Example 1 — Triangle (n=3)

$ Input: n = 3

› Output: 6

💡 Note: Total ways = 2³ = 8. Non-collision ways = 2 (all clockwise or all counterclockwise). Collision ways = 8 - 2 = 6.

Example 2 — Square (n=4)

$ Input: n = 4

› Output: 14

💡 Note: Total ways = 2⁴ = 16. Non-collision ways = 2. Collision ways = 16 - 2 = 14.

Example 3 — Edge Case (n=1000000000)

$ Input: n = 1000000000

› Output: 49

💡 Note: Using modular arithmetic: 2¹⁰⁰⁰⁰⁰⁰⁰⁰⁰ mod (10⁹+7) = 51, so answer is (51-2) mod (10⁹+7) = 49.

Constraints

1 ≤ n ≤ 10⁹
Answer modulo 10⁹ + 7

Visualization

Tap to expand

Understanding the Visualization

Setup

n monkeys on polygon vertices, each moves to adjacent vertex

Movement

Each monkey chooses clockwise or counterclockwise

Count Collisions

Return number of ways with at least one collision

Key Takeaway

🎯 Key Insight: Only 2 out of 2^n movement patterns avoid collisions

Asked in

G Google 25 M Meta 20 a Amazon 15

The key insight is using complementary counting: out of 2^n total movement ways, only 2 avoid collisions (all clockwise or all counterclockwise). Best approach uses mathematical formula 2^n - 2 with fast exponentiation. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula (Optimal)	O(log n)	O(1)	Use complementary counting: total ways minus collision-free ways
Brute Force Simulation	O(2^n × n)	O(n)	Generate all possible movement combinations and count collisions

Mathematical Formula (Optimal) — Algorithm Steps

Calculate total possible movements: 2^n
Identify collision-free cases: all clockwise OR all counterclockwise
Apply complementary counting: 2^n - 2
Handle modulo arithmetic with fast exponentiation

Visualization

Tap to expand

Step-by-Step Walkthrough

Total Ways

Each monkey has 2 choices: 2^n total combinations

No-Collision Cases

Only 2 ways: all clockwise or all counterclockwise

Answer

Collision ways = 2^n - 2

Code -

solution.c — C

#include <stdio.h>

long long power(long long base, int exp, int mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}

int solution(int n) {
    const int MOD = 1000000007;
    
    // Fast exponentiation to compute 2^n mod MOD
    long long totalWays = power(2, n, MOD);
    
    // Non-collision ways: 2 (all clockwise or all counterclockwise)
    int nonCollisionWays = 2;
    
    // Collision ways: total - non_collision
    int collisionWays = (totalWays - nonCollisionWays + MOD) % MOD;
    
    return collisionWays;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Fast exponentiation to compute 2^n mod (10^9 + 7)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler