Count Collisions of Monkeys on a Polygon

Medium
1318.

Count Collisions of Monkeys on a Polygon

Count Collisions of Monkeys on a Polygon is a medium coding problem on math and recursion, asked in Amazon and Google interviews.

A regular polygon has n vertices numbered 0 to n - 1 clockwise, and one monkey sits on every vertex. At the same moment every monkey moves to one of its two neighbouring vertices — clockwise or anticlockwise.

A collision happens if, after the move, two monkeys share a vertex, or if two monkeys cross each other on an edge.

Return the number of ways the monkeys can move so that at least one collision happens, modulo 10^9 + 7.

Example 1

Input
n = 3
Output
6
Explanation
There are 2³ = 8 ways to move; only 'all clockwise' and 'all anticlockwise' avoid a collision.

Example 2

Input
n = 4
Output
14

Example 3

Input
n = 1000000000
Output
140624999

Constraints

  • 3 <= n <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var monkeyMove = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Collisions of Monkeys on a Polygon — Solution

Count Collisions of Monkeys on a Polygon solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Collisions of Monkeys on a Polygon is a medium coding problem on math and recursion, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Math, Recursion
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A regular polygon has n vertices numbered 0 to n - 1 clockwise, and one monkey sits on every vertex. At the same moment every monkey moves to one of its two neighbouring vertices — clockwise or anticlockwise.

A collision happens if, after the move, two monkeys share a vertex, or if two monkeys cross each other on an edge.

Return the number of ways the monkeys can move so that at least one collision happens, modulo 10^9 + 7.

Example 1

Input: n = 3
Output: 6
Explanation: There are 2³ = 8 ways to move; only 'all clockwise' and 'all anticlockwise' avoid a collision.

Example 2

Input: n = 4
Output: 14

Example 3

Input: n = 1000000000
Output: 140624999

Constraints

  • 3 <= n <= 10^9

Hints for Count Collisions of Monkeys on a Polygon

  1. Hint 1

    Count the complement: in how many ways can the monkeys move with no collision at all?

  2. Hint 2

    If one monkey goes clockwise and its clockwise neighbour goes anticlockwise, they cross on the edge between them. What does that force around the polygon?

  3. Hint 3

    Only 'everyone clockwise' and 'everyone anticlockwise' are collision-free, so the answer is 2^n - 2 — compute the power by repeated squaring.

How to solve Count Collisions of Monkeys on a Polygon

Every monkey has two choices, 2^n ways in total, and exactly two of them — all clockwise or all anticlockwise — avoid every collision. The answer is (2^n - 2) mod (10^9 + 7).

Approach

  1. Compute 2^n mod M with binary exponentiation (M = 10^9 + 7).
  2. Subtract 2 and add M before reducing again, so the result never goes negative.

Why it works

If all monkeys move the same way, the configuration just rotates: no vertex is shared and no two monkeys use the same edge. Otherwise, going around the polygon there is some monkey moving clockwise whose clockwise neighbour moves anticlockwise; they swap along their shared edge and collide. So the collision-free moves are exactly the two uniform ones, and all other 2^n - 2 moves contain a collision.

Complexity

  • Time — O(log n)
  • Space — O(1)

Pitfalls

  • 2^n mod M can be 0 or 1, so 2^n mod M - 2 can be negative — add M before taking the modulus again.
  • n reaches 10^9: a loop that doubles n times is too slow; use repeated squaring.
  • Multiply two residues in 64 bits (or split the multiplication in JavaScript).

Reference solution

Python

def monkeyMove(n: int) -> int:
    MOD = 10 ** 9 + 7
    return (pow(2, n, MOD) - 2) % MOD

Java

public static int monkeyMove(int n) {
    final long MOD = 1000000007L;
    long r = 1, b = 2;
    int e = n;
    while (e > 0) {
        if ((e & 1) == 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return (int) ((r - 2 + MOD) % MOD);
}

C++

int monkeyMove(int n) {
    const long long MOD = 1000000007LL;
    long long r = 1, b = 2;
    int e = n;
    while (e > 0) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return (int) ((r - 2 + MOD) % MOD);
}

JavaScript

var monkeyMove = function(n) {
    var MOD = 1000000007;
    var mulMod = function(a, b) {
        var hi = Math.floor(b / 65536), lo = b % 65536;
        return ((a * hi) % MOD * 65536 + a * lo) % MOD;
    };
    var r = 1, b = 2, e = n;
    while (e > 0) {
        if (e % 2 === 1) r = mulMod(r, b);
        b = mulMod(b, b);
        e = Math.floor(e / 2);
    }
    return (r - 2 + MOD) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Recursion