Minimum Cuts to Divide a Circle

Difficulty: Easy | Acceptance: 56.20% | Paid: No Topics: Math, Geometry

Given an integer n, return the minimum number of cuts needed to divide a circle into n equal pieces.

A valid cut is a straight line that passes through the center of the circle and divides the circle into two pieces.

• Examples
• Constraints
• Mathematical Logic
• Bitwise Manipulation

Examples

Example 1

Input:

n = 4

Output:

2

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

Example 2

Input:

n = 3

Output:

3

Explanation: At least 3 cuts are needed to divide the circle into 3 equal slices. It can be shown that less than 3 cuts cannot result in 3 slices of equal size and shape. Also note that the first cut will not divide the circle into distinct parts.

Constraints

- 1 <= n <= 100

Mathematical Logic

Intuition The problem relies on the parity of the number of pieces n. If n is 1, no cuts are needed. If n is even, we can cut through the center n/2 times to create n pieces (each cut creates 2 pieces). If n is odd, we cannot cut through the center to get an odd number of pieces (except 1), so we need n cuts.

Steps

• Check if n is 1. If so, return 0.
• Check if n is even. If so, return n / 2.
• Otherwise, n is odd, return n.

class Solution:
    def numberOfCuts(self, n: int) -> int:
        if n == 1:
            return 0
        if n % 2 == 0:
            return n // 2
        return n

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This is the most straightforward approach using basic arithmetic checks.

Bitwise Manipulation

Intuition We can optimize the parity check and division using bitwise operators. Checking if a number is odd is equivalent to checking if the least significant bit is set (n & 1). Dividing an even number by 2 is equivalent to a right shift by 1 (n >> 1).

Steps

• If n is 1, return 0.
• If n is odd (n & 1), return n.
• If n is even, return n >> 1.

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

Complexity

• Time: O(1)
• Space: O(1)
• Notes: This approach is functionally identical to the mathematical logic but uses bitwise operations which can be slightly faster at the CPU level.