We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Cuts to Divide a Circle

Number: 2575

Difficulty: Easy

Paid? No

Companies: tcs

Problem Description

Given a circle and an integer n, determine the minimum number of straight-line cuts needed to divide the circle into n equal slices. A valid cut can either be a straight line going through the center and touching two points on the circle’s edge or a straight line starting from the center and touching a single point on the edge.

Key Insights

  • If n is 1, no cut is needed.
  • If n is even, the circle can be divided into n equal parts using n/2 diameter cuts.
  • If n is odd (and n is greater than 1), the only way to achieve n equal slices is to make n cuts.
  • The problem essentially reduces to basic arithmetic based on whether n is even or odd.

Space and Time Complexity

Time Complexity: O(1) Space Complexity: O(1)

Solution

We check for the base case when n equals 1, which requires 0 cuts. For any other n:

  • If n is even, each diameter cut will create 2 equal slices, so the minimum number of cuts is n/2.
  • If n is odd, each cut contributes to one slice without the benefit of pairing, hence n cuts are needed.

This solution uses simple conditional logic with constant time arithmetic operations.

Code Solutions

# Define a function to calculate minimum cuts for n equal slices.
def minimum_cuts(n: int) -> int:
    # If there is only one slice, no cut is needed.
    if n == 1:
        return 0
    # If n is even, every cut (diameter) produces 2 slices.
    if n % 2 == 0:
        return n // 2
    # For any odd n greater than 1, n cuts are needed.
    return n

# Example usage:
print(minimum_cuts(4))  # Expected output: 2
print(minimum_cuts(3))  # Expected output: 3
← Back to All Questions