Minimum Cuts to Divide a Circle

Problem#

Return the minimum number of straight cuts needed to divide a circle into n equal slices.

Examples#

• n=4 → 2 (two perpendicular diameters).
• n=3 → 3; n=1 → 0.

Constraints#

• 1 <= n <= 100.

Approach#

If n == 1, no cuts needed. Otherwise, each diameter cut produces 2 slices; a chord cut produces 1 (if it doesn’t pass through the center, two chord cuts can’t always combine cleanly). Diameters work iff n is even — n/2 of them. For odd n, each cut must be a separate non-diameter chord radiating from the center — n cuts.

Solution#

class Solution {
public:
    int numberOfCuts(int n) {
        if (n == 1) return 0;
        return (n % 2 == 0) ? n / 2 : n;
    }
};

func numberOfCuts(n int) int {
    if n == 1 {
        return 0
    }
    if n%2 == 0 {
        return n / 2
    }
    return n
}

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

function numberOfCuts(n) {
    if (n === 1) return 0;
    return n % 2 === 0 ? n / 2 : n;
}

class Solution {
    public int numberOfCuts(int n) {
        if (n == 1) return 0;
        return (n % 2 == 0) ? n / 2 : n;
    }
}

function numberOfCuts(n: number): number {
    if (n === 1) return 0;
    return n % 2 === 0 ? n / 2 : n;
}

Editorial#

The only non-trivial observation: a single straight cut through the center produces 2 slices, but two cuts at different angles share the center, so 3 cuts give 6 slices, etc. — only even slice counts are achievable via diameters. For odd slice counts, all cuts must be radii (half-diameters) at different angles, hence one per slice.

Complexity#

• Time: O(1).
• Space: O(1).

Concept revision#

Related#

• Nim Game
• Bulb Switcher