Minimum Cuts to Divide a Circle — LeetCode 2481 Python Solution

The problem

A valid cut in a circle can be: A cut that is represented by a straight line that touches two points on the edge of the circle and passes through its center, or A cut that is represented by a straight line that touches one point on the edge of the circle and its center. Some valid and invalid cuts are shown in the figures below.

Example

Input

n = 4

Output

2

Explanation

The above figure shows how cutting the circle twice through the middle divides it into 4 equal slices.

Python solution

class Solution:
    def numberOfCuts(self, n: int) -> int:
        return n if (n > 1 and n & 1) else n >> 1

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 2481. Minimum Cuts to Divide a Circle is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math and Geometry.

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

Related problems