How hard is LeetCode 2550. Count Collisions of Monkeys on a Polygon?

LeetCode 2550. Count Collisions of Monkeys on a Polygon is rated Medium on LeetCode.

What is the time complexity of LeetCode 2550. Count Collisions of Monkeys on a Polygon?

The Python solution on this page runs in O(\log n), where n is the number of monkeys.

What is the space complexity of LeetCode 2550. Count Collisions of Monkeys on a Polygon?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 2550. Count Collisions of Monkeys on a Polygon cover?

LeetCode 2550. Count Collisions of Monkeys on a Polygon is tagged Recursion and Math on LeetCode.

Count Collisions of Monkeys on a Polygon — LeetCode 2550 Python Solution

MediumRecursionMath

Problem: #2550
Pattern: Math and Number Theory
Reading time: 2 min
Source: leetcode.com

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

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(\log n), where n is the number of monkeys
Space	O(1) auxiliary

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 2550. Count Collisions of Monkeys on a Polygon is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2550. Count Collisions of Monkeys on a Polygon?: LeetCode 2550. Count Collisions of Monkeys on a Polygon is rated Medium on LeetCode.
What is the time complexity of LeetCode 2550. Count Collisions of Monkeys on a Polygon?: The Python solution on this page runs in O(\log n), where n is the number of monkeys.
What is the space complexity of LeetCode 2550. Count Collisions of Monkeys on a Polygon?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2550. Count Collisions of Monkeys on a Polygon cover?: LeetCode 2550. Count Collisions of Monkeys on a Polygon is tagged Recursion and Math on LeetCode.