Count Collisions of Monkeys on a Polygon

Medium

Asked by:

49 views

Topics:

Bit Manipulation

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 10⁹+ 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 <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for `n`, the number of monkeys (or sides of the polygon)? Is it safe to assume n will always be a positive integer?
If n is equal to 1 or 2, are collisions possible? If not, what should I return in those edge cases?
Are we only concerned with the number of collisions, or do we need to identify which monkeys collide?
What is the expected return type? Specifically, should I return the result modulo some prime number, or just the raw number of collisions?
Can you please clarify the definition of a 'collision'? Does a collision occur if *any* two monkeys choose the same adjacent vertex, or does it require *all* monkeys to choose the same vertex?

Brute Force Solution

Approach

The brute force way to solve this monkey collision problem is to try every possible arrangement of monkeys around the polygon. We'll manually check each arrangement to see if any monkeys are about to collide.

Here's how the algorithm would work step-by-step:

Consider the first monkey. It can go in one of two directions: clockwise or counter-clockwise.
Then, consider the second monkey. It also has two choices: clockwise or counter-clockwise.
Continue this process for every single monkey, making sure to track each monkey's direction choice.
Each time we've assigned a direction for every monkey, we have one possible arrangement.
For each of these arrangements, check if any two monkeys are headed toward each other (that is, about to collide).
If no monkeys are about to collide in a given arrangement, that arrangement is safe.
After checking all possible arrangements, count the number of arrangements where at least two monkeys are about to collide. This is the number of ways the monkeys collide.

Code Implementation

def count_monkey_collisions_brute_force(number_of_monkeys):
    total_arrangements = 2 ** number_of_monkeys
    collision_count = 0

    for arrangement_index in range(total_arrangements):
        directions = []
        # Determine the direction of each monkey
        for monkey_index in range(number_of_monkeys):
            if (arrangement_index >> monkey_index) & 1:
                directions.append(1)  # Clockwise
            else:
                directions.append(-1)  # Counter-clockwise

        about_to_collide = False
        # Check for collisions for this arrangement
        for first_monkey_index in range(number_of_monkeys):
            for second_monkey_index in range(first_monkey_index + 1, number_of_monkeys):
                # Collision occurs if monkeys are moving towards each other
                if directions[first_monkey_index] == 1 and directions[second_monkey_index] == -1:
                    about_to_collide = True
                elif directions[first_monkey_index] == -1 and directions[second_monkey_index] == 1:
                    about_to_collide = True
        if about_to_collide:
            collision_count += 1

    return collision_count

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible direction combinations for each monkey. Since each of the n monkeys can move in one of two directions (clockwise or counter-clockwise), there are 2^n total possible arrangements. For each arrangement, we must check if any pair of monkeys will collide, taking O(n) time to check all n monkeys. Even if the collision check is optimized out, the dominating cost is generating all 2^n arrangements of monkeys. Therefore, the overall time complexity is O(2^n).

Space Complexity

O(N) – The brute force solution involves generating all possible arrangements of monkey directions. While the direction choices themselves might be stored implicitly through iteration, the description indicates that each arrangement needs to be checked. This implies storing the direction (clockwise or counter-clockwise) of each monkey in a temporary array of size N, where N is the number of monkeys (or vertices of the polygon). Although not explicitly stated, checking if the arrangement causes a collision will likely require some form of storing the arrangement. Therefore, auxiliary space of O(N) is used to represent the arrangement being checked.

Optimal Solution

Approach

The problem asks about monkeys moving around a polygon and potentially colliding. Instead of simulating each monkey's movement, we can use math to find the total number of ways monkeys can move without any restrictions, and then subtract the number of ways where they all move in the same direction to avoid collisions. This simplifies the problem dramatically.

Here's how the algorithm would work step-by-step:

First, consider all the possible ways the monkeys can move. Each monkey has two choices: clockwise or counter-clockwise.
Calculate the total number of possible movement combinations for all the monkeys. Since each monkey has two options, you'll raise 2 to the power of the number of monkeys.
Now, consider the scenarios where NO monkeys collide. This only happens if all monkeys move in the same direction: either all clockwise, or all counter-clockwise.
Subtract these two collision-free scenarios (all clockwise, all counter-clockwise) from the total number of possible movement combinations you calculated earlier.
The result is the number of movement combinations where at least two monkeys will collide.

Code Implementation

def count_collisions(number_of_monkeys):
    modulo_value = 10**9 + 7

    # Calculate the total possible movement combinations.
    total_combinations = pow(2, number_of_monkeys, modulo_value)

    # Subtract the scenarios where all monkeys move in the same direction
    collision_free_scenarios = 2

    number_of_collisions = (total_combinations - collision_free_scenarios) % modulo_value

    return number_of_collisions

Big(O) Analysis

Time Complexity

O(1) – The algorithm calculates 2 raised to the power of n (number of monkeys) and then subtracts 2. The power operation can be implemented in O(1) time using exponentiation by squaring with a modular exponentiation. Alternatively, if raising 2 to the nth power is precomputed or achieved with bit shifting, this part is still O(1). Finally, subtracting 2 is a constant time operation. Therefore, the overall time complexity is O(1), as the number of operations is independent of the input size n.

Space Complexity

O(1) – The provided solution calculates the result directly using arithmetic operations. It does not create any auxiliary data structures like arrays, lists, or hash maps. The space used is limited to storing a few variables for intermediate calculations such as total possible combinations and the number of collision-free scenarios, irrespective of the number of monkeys, N. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
N = 1 (Only one monkey)	Return 0 since there is only one monkey and no collision is possible.
N = 2 (Only two monkeys)	Return 2, as both monkeys must choose to go to a vertex, resulting in a collision.
Large N causing potential overflow in power calculation	Use modular arithmetic throughout the calculation to prevent integer overflow.
N = 0	Throw an IllegalArgumentException or return 0, based on the problem description.
Very large N that could approach memory limitations if intermediate results are stored	Ensure that intermediate calculations use the modulo operator (%) to keep the numbers within reasonable bounds.
Negative values of N	Throw an IllegalArgumentException as the number of monkeys cannot be negative.
N equals the modulo value	Applying the modulo operator after each multiplication is crucial to prevent overflow and incorrect results.
Modulo value is 1	Return 0, as all results modulo 1 are 0.

N = 1 (Only one monkey)

How to Handle:

Return 0 since there is only one monkey and no collision is possible.

N = 2 (Only two monkeys)

How to Handle:

Return 2, as both monkeys must choose to go to a vertex, resulting in a collision.

Large N causing potential overflow in power calculation

How to Handle:

Use modular arithmetic throughout the calculation to prevent integer overflow.

N = 0

How to Handle:

Throw an IllegalArgumentException or return 0, based on the problem description.

Very large N that could approach memory limitations if intermediate results are stored

How to Handle:

Ensure that intermediate calculations use the modulo operator (%) to keep the numbers within reasonable bounds.

Negative values of N

How to Handle:

Throw an IllegalArgumentException as the number of monkeys cannot be negative.

N equals the modulo value

How to Handle:

Applying the modulo operator after each multiplication is crucial to prevent overflow and incorrect results.

Modulo value is 1

How to Handle:

Return 0, as all results modulo 1 are 0.