Lazy Caterer's sequence

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) = \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.

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.
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.
Recurrence relation: The total number of pieces after n cuts is given by the recurrence relation: f(n) = n + f(n-1)
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)
Initial state: When there are no cuts (n = 0), there is just one whole piece: f(0) = 1
Summation: Combining everything, we get: f(n) = 1 + (1 + 2 + 3 + ... + n)
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
Final formula: Substituting this into our expansion: f(n) = 1 + n(n + 1) / 2

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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");
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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.

Problem#

Solution#

Method 1 - Using Mathematics#

Proof#

Code#

Complexity#