2481. Minimum Cuts to Divide a Circle
Description
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.
Given the integer n
, return the minimum number of cuts needed to divide a circle into n
equal slices.
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
Solutions
Solution 1: Case Discussion
- When $n=1$, no cutting is needed, so the number of cuts is $0$;
- When $n$ is odd, there is no collinear situation, and at least $n$ cuts are needed;
- When $n$ is even, they can be collinear in pairs, and at least $\frac{n}{2}$ cuts are needed.
In summary, we can get:
$$ \textit{ans} = \begin{cases} n, & n \gt 1 \textit{ and } n \textit{ is odd} \ \frac{n}{2}, & n \textit{ is even} \ \end{cases} $$
The time complexity is $O(1)$, and the space complexity is $O(1)$.
1 2 3 |
|
1 2 3 4 5 |
|
1 2 3 4 5 6 |
|
1 2 3 4 5 6 |
|
1 2 3 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 |
|