problemunknownuncategorized

Lazy Caterer's sequence

Updated: Mar 12, 2025

Problem

Given a circular (or regular polygon) cake and a knife by which you can only cut vertically, find the maximum number of pieces of cake you can get by making n cuts. Write a program to do that.

Solution

Method 1 - Using Mathematics

The solution to this is very simple, if you know mathematics 😜.

More on wikipedia - http://en.wikipedia.org/wiki/Lazy_caterer%27s_sequence.

The Lazy Caterer's sequence describes the maximum number of pieces a circle (or a pancake) can be divided into with a given number of straight cuts. The formula to determine the maximum number of pieces from ( n ) cuts is:

P(n)=n(n+1)2+1P(n) = \frac{n(n + 1)}{2} + 1

Proof

When a circle is cut n times to produce the maximum number of pieces, represented as f(n), each new cut must be considered. The number of pieces before the n-th cut is f(n-1), and the number of pieces added by the n-th cut is n.

  1. Adding the nth cut: To obtain the maximum number of pieces, the n-th cut line should cross all the previous cut lines inside the circle but should not cross any intersections of the previous cut lines. Thus, the n-th line itself intersects the previous n-1 lines and is divided into n segments.

  2. New number of pieces: Each new segment created by the n-th cut divides one existing piece into two parts. Therefore, exactly n new pieces are added by the n-th cut.

  3. Recurrence relation: The total number of pieces after n cuts is given by the recurrence relation: f(n) = n + f(n-1)

  4. Expanding the recurrence relation: If we repeatedly expand the recurrence relation, we get: f(n) = n + f(n-1) = n + (n-1) + f(n-2) = n + (n-1) + (n-2) + ... + 1 + f(0)

  5. Initial state: When there are no cuts (n = 0), there is just one whole piece: f(0) = 1

  6. Summation: Combining everything, we get: f(n) = 1 + (1 + 2 + 3 + ... + n)

  7. Arithmetic progression formula: The sum of the first n natural numbers can be given by the formula for the sum of an arithmetic progression: 1 + 2 + 3 + ... + n = n(n + 1) / 2

  8. Final formula: Substituting this into our expansion: f(n) = 1 + n(n + 1) / 2

Code

Java
public class LazyCaterer {

    // Function to calculate the maximum number of pieces with n cuts
    public static int lazyCaterer(int n) {
        return (n * (n + 1)) / 2 + 1;
    }

    public static void main(String[] args) {
        int cuts = 5; // Example: Number of cuts
        int maxPieces = lazyCaterer(cuts);
        System.out.println("The maximum number of pieces with " + cuts + " cuts is: " + maxPieces);

        // Additional test cases
        for (int i = 0; i <= 10; i++) {
            System.out.println(i + " cuts result in " + lazyCaterer(i) + " pieces");
        }
    }
}
Python
def lazy_caterer(n):
    return (n * (n + 1)) // 2 + 1

# Test the function
cuts = 5
max_pieces = lazy_caterer(cuts)
print(f"The maximum number of pieces with {cuts} cuts is: {max_pieces}")

# Additional tests
for i in range(10):
    print(f"{i} cuts result in {lazy_caterer(i)} pieces")

Complexity

  • ⏰ Time complexity: O(1) as we are using the formula.
  • 🧺 Space complexity: O(1) as we are using only a few variables.

Comments