# Minimum Cuts to Divide a Circle
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-cuts-to-divide-a-circle)
Canonical: https://scaleengineer.com/dsa/problems/minimum-cuts-to-divide-a-circle
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Companies:** [tcs](https://scaleengineer.com/companies/tcs)
---
## 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.

![](https://assets.glich.co/dsa/minimum-cuts-to-divide-a-circle/image0.png) 

Given the integer `n`, return _the **minimum** number of cuts needed to divide a circle into_ `n` _equal slices_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-cuts-to-divide-a-circle/image1.png) 

**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:**

![](https://assets.glich.co/dsa/minimum-cuts-to-divide-a-circle/image2.png) 

**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`

# Approaches
## Iterative Approach
This approach simulates finding the minimum number of cuts by iterating from 1 up to `n` and checking at each step if the current number of cuts is sufficient to create `n` equal slices. It correctly distinguishes between the strategies for even and odd `n` but does so within a loop, making it less efficient than a direct calculation.
**Time:** O(n) - In the worst-case scenario (when `n` is odd), the loop will run `n` times before finding the answer. · **Space:** O(1) - The algorithm uses a constant amount of extra space, regardless of the input size `n`.
**Pros:** Simple to understand and implement as it directly translates a trial-and-error thought process.; Correctly solves the problem for all valid inputs.
**Cons:** Inefficient due to the unnecessary loop. The problem has a direct mathematical solution that doesn't require iteration.; The time complexity is linear, while an optimal constant-time solution exists.
### Explanation
The core idea is to test each possible number of cuts, `c`, starting from 1.

*   First, we handle the edge case where `n = 1`, which requires 0 cuts.
*   Then, we loop `c` from 1 to `n`.
*   Inside the loop, we consider two cases based on whether `n` is even or odd.
    *   **If `n` is even:** We know that `c` diameter cuts produce `2 * c` slices. We check if `2 * c` equals `n`. If it does, `c` is the minimum number of cuts required, and we can return it.
    *   **If `n` is odd:** Diameter cuts cannot produce an odd number of slices. We must use `n` radius cuts. So, we check if the current number of cuts `c` is equal to `n`. If it is, we return `c`.
*   This process guarantees finding the smallest `c` that satisfies the condition.

```java
class Solution {
    public int numberOfCuts(int n) {
        if (n == 1) {
            return 0;
        }
        // This loop iterates to find the minimum number of cuts.
        for (int c = 1; c <= n; c++) {
            // Case for even n: we can use diameter cuts.
            if (n % 2 == 0) {
                if (c * 2 == n) {
                    return c;
                }
            } 
            // Case for odd n: we must use radius cuts.
            else {
                if (c == n) {
                    return c;
                }
            }
        }
        return -1; // Should not be reached
    }
}
```
### Algorithm
- Handle the base case: if `n = 1`, return 0.
- Loop through the number of cuts `c` from 1 to `n`.
- Check if `n` is even. If so, check if `2 * c == n`. If true, `c` is the answer, so return `c`.
- Check if `n` is odd. If so, check if `c == n`. If true, `c` is the answer, so return `c`.

## O(1) Mathematical Solution
This optimal approach leverages a direct mathematical formula derived from the geometric properties of the cuts. By analyzing the two types of cuts, we can determine the minimum number required for any given `n` in constant time, making it highly efficient.
**Time:** O(1) - The solution consists of a few simple checks and arithmetic operations that take constant time, regardless of the value of `n`. · **Space:** O(1) - No additional space is allocated that depends on the input size.
**Pros:** Extremely efficient, providing the answer in constant time.; Optimal solution in terms of both time and space complexity.; Simple and concise code.
**Cons:** Requires a bit of mathematical and geometric insight to derive the formula, which might not be immediately obvious.
### Explanation
The solution is based on a simple analysis of how to achieve `n` equal slices with minimum cuts.

*   **Case 1: `n = 1`**
    The circle is already one slice, so no cuts are needed. The result is 0.

*   **Case 2: `n` is even**
    We can use diameter cuts. Each diameter cut passes through the center and creates `2` slices. To get `n` slices, we need `n / 2` diameter cuts. For example, to get 4 slices, we need `4 / 2 = 2` cuts. This is always more efficient than using `n` radius cuts (since for `n >= 2`, `n/2 <= n`). So, the answer is `n / 2`.

*   **Case 3: `n` is odd (and `n > 1`)**
    Diameter cuts always result in an even number of slices. Therefore, we cannot use them to get an odd number of slices. We must use radius cuts (from the center to the edge). To get `n` equal slices, we need to make `n` such cuts. For example, to get 3 slices, we need 3 cuts. So, the answer is `n`.

This logic can be implemented with a simple conditional check.
```java
class Solution {
    public int numberOfCuts(int n) {
        // Case 1: n = 1, no cuts needed.
        if (n == 1) {
            return 0;
        }
        // Case 2: n is even, use n/2 diameter cuts.
        if (n % 2 == 0) {
            return n / 2;
        } 
        // Case 3: n is odd, use n radius cuts.
        else {
            return n;
        }
    }
}
```
### Algorithm
- Check for the special case `n = 1`. If true, return 0.
- Check if `n` is divisible by 2 (i.e., even). If true, return `n / 2`.
- If `n` is not even (i.e., odd), return `n`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int NumberOfCuts(int n) {
        return n > 1 && n % 2 == 1 ? n : n >> 1;
    }
}
```

### Java

```java
class Solution {
public
  int numberOfCuts(int n) { return n > 1 && n % 2 == 1 ? n : n >> 1; }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfCuts(int n) { return n > 1 && n % 2 == 1 ? n : n >> 1; }
};

```

### Python

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

```