Teaching Kids Programming – Minimum Cuts to Divide a Circle

Teaching Kids Programming: Videos on Data Structures and Algorithms

Minimum Cuts to Divide a Circle

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

Hints:
Think about odd and even values separately.
When will we not have to cut the circle at all?

Minimum Cuts to Divide a Circle

The special case when N=1 meaning that we need zero cuts. And if N is odd, we can cut the entire circle into N equal slices with half cuts, otherwise, we can do N//2 full cuts for even equal slices. O(1) time and space obviously as it is just math calculation

1
2
3
4
5
6
7

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

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

–EOF (The Ultimate Computing & Technology Blog) —