#2481

Easy

LeetCode Problem Workspace

Minimum Cuts to Divide a Circle

Calculate the fewest cuts required to divide a circle into n equal slices using math and geometric reasoning efficiently.

math geometry

Problem Statement

Given a circle, you need to slice it into exactly n equal parts. Each cut passes through the center and can divide multiple slices at once. Your goal is to find the minimum number of straight cuts required so that all slices are of equal size.

Constraints include 1 <= n <= 100. Consider the difference between even and odd n: even numbers allow dividing in halves, whereas odd numbers often require individual cuts. Return the minimum number of cuts for any given n.

Examples

Example 1

Input: n = 4

Output: 2

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

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

Solution Approach

Check if n is even

If n is even, you can achieve equal slices with n/2 cuts. Each cut passes through the center, splitting two slices at a time. This geometric insight directly reduces the number of cuts needed.

Handle odd n values

If n is odd, each cut only creates one new slice through the center, so you need n cuts. Trying fewer cuts fails to produce equal slices, revealing the pattern failure mode for odd numbers.

Return minimum cuts

Apply the conditional logic: return n/2 for even n and n for odd n. This provides a direct, math-plus-geometry solution without iterating through unnecessary divisions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) because the solution is a single conditional check based on parity. Space complexity is O(1) as no extra data structures are needed.

What Interviewers Usually Probe

Asks for the minimum number of cuts for small n like 4 or 5.
Hints at separating odd and even n to reduce overcutting.
Checks if candidate can explain why fewer cuts fail for odd n.

Common Pitfalls or Variants

Common pitfalls

Assuming each cut always doubles slices, which fails for odd n.
Ignoring the center-cross requirement, leading to invalid slices.
Confusing minimum number of cuts with total slices created.

Follow-up variants

Determine cuts if slices must be non-overlapping sectors of different sizes.
Find minimum cuts for a circle with concentric rings instead of one layer.
Calculate cuts if the circle can only be cut along specific angles.

FAQ

What is the minimum number of cuts to divide a circle into n equal slices?

For even n, it is n/2 cuts. For odd n, it requires n cuts because each cut creates only one new slice.

Does the first cut always split the circle into two slices?

Not necessarily. For odd n greater than 1, the first cut may not produce equal slices, highlighting why additional cuts are needed.

Why does the solution differentiate between odd and even n?

Even n allows halving the circle efficiently, while odd n cannot be split symmetrically with fewer cuts, reflecting the problem's math-plus-geometry pattern.

Can you use diagonal or curved cuts instead of straight lines?

No, the problem requires straight cuts through the center. Non-straight cuts invalidate equal slice formation.

What is a common mistake when counting minimum cuts?

Counting total slices instead of actual cuts often leads to overestimation, especially for odd n values.

terminal

Solution

Solution 1: Case Discussion

- When $n=1$, no cutting is needed, so the number of cuts is $0$;

1

2

3

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

Continue Practicing

#2280 minimum lines to represent a line chart #2249 count lattice points inside a circle #2101 detonate the maximum bombs