Skip to content
Welcome to contribute to Chinese-to-English translation! For more details, please refer to CONTRIBUTING.md.

# 15.4 Maximum Product Cutting Problem

Question

Given a positive integer \(n\), split it into the sum of at least two positive integers and find the maximum product of the resulting integers, as shown in Figure 15-13.

Figure 15-13 Problem definition of max product cutting

Suppose we split \(n\) into \(m\) integer factors, where the \(i\)-th factor is denoted as \(n_i\), that is

\[ n = \sum_{i=1}^{m}n_i \]

The goal of this problem is to find the maximum product of all integer factors, namely

\[ \max(\prod_{i=1}^{m}n_i) \]

We need to determine how many parts \(m\) there should be and what each \(n_i\) should be.

### 1. Determining the Greedy Strategy

As a rule of thumb, the product of two integers is often greater than their sum. Suppose we split off a factor of \(2\) from \(n\); the resulting product is \(2(n-2)\). We compare this product with \(n\):

\[ \begin{aligned} 2(n-2) & \geq n \newline 2n - n - 4 & \geq 0 \newline n & \geq 4 \end{aligned} \]

As shown in Figure 15-14, when \(n \geq 4\), splitting out a \(2\) will increase the product, which indicates that integers greater than or equal to \(4\) should all be split.

Greedy strategy one: If the splitting scheme contains a factor \(\geq 4\), it should be split further. The final splitting scheme should contain only the factors \(1\), \(2\), and \(3\).

Figure 15-14 Splitting causes product to increase

Next, consider which factor is optimal. Among the three factors \(1\), \(2\), and \(3\), clearly \(1\) is the worst, because \(1 \times (n-1) < n\) always holds, meaning splitting out \(1\) will actually decrease the product.

As shown in Figure 15-15, when \(n = 6\), we have \(3 \times 3 > 2 \times 2 \times 2\). This means that splitting out \(3\) is better than splitting out \(2\).

Greedy strategy two: In the splitting scheme, there should be at most two \(2\)s, because three \(2\)s can always be replaced by two \(3\)s to obtain a larger product.

Figure 15-15 Optimal splitting factor

In summary, the following greedy strategies can be derived.

1. Input integer \(n\), continuously split out factor \(3\) until the remainder is \(0\), \(1\), or \(2\).
2. When the remainder is \(0\), it means \(n\) is a multiple of \(3\), so no further action is needed.
3. When the remainder is \(2\), do not split it further; keep it as is.
4. When the remainder is \(1\), since \(2 \times 2 > 1 \times 3\), replace the final \(3\) and the remaining \(1\) with two \(2\)s.

### 2. Code Implementation

As shown in Figure 15-16, we do not need loops to split the integer. Instead, we use integer division to obtain the number of \(3\)s, denoted by \(a\), and the modulo operation to obtain the remainder \(b\), giving:

\[ n = 3 a + b \]

Please note that for the edge case of \(n \leq 3\), a \(1\) must be split out, with product \(1 \times (n - 1)\).

Python C++Java C#Go Swift JS TS Dart Rust C Kotlin Ruby
max_product_cutting.py

    def max_product_cutting(n: int) -> int:
        """Max product cutting: Greedy algorithm"""
        # When n <= 3, must cut out a 1
        if n <= 3:
            return 1 * (n - 1)
        # Greedily cut out 3, a is the number of 3s, b is the remainder
        a, b = n // 3, n % 3
        if b == 1:
            # When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return int(math.pow(3, a - 1)) * 2 * 2
        if b == 2:
            # When the remainder is 2, do nothing
            return int(math.pow(3, a)) * 2
        # When the remainder is 0, do nothing
        return int(math.pow(3, a))

max_product_cutting.cpp

    /* Max product cutting: Greedy algorithm */
    int maxProductCutting(int n) {
        // When n <= 3, must cut out a 1
        if (n <= 3) {
            return 1 * (n - 1);
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        int a = n / 3;
        int b = n % 3;
        if (b == 1) {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return (int)pow(3, a - 1) * 2 * 2;
        }
        if (b == 2) {
            // When the remainder is 2, do nothing
            return (int)pow(3, a) * 2;
        }
        // When the remainder is 0, do nothing
        return (int)pow(3, a);
    }

max_product_cutting.java

    /* Max product cutting: Greedy algorithm */
    int maxProductCutting(int n) {
        // When n <= 3, must cut out a 1
        if (n <= 3) {
            return 1 * (n - 1);
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        int a = n / 3;
        int b = n % 3;
        if (b == 1) {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return (int) Math.pow(3, a - 1) * 2 * 2;
        }
        if (b == 2) {
            // When the remainder is 2, do nothing
            return (int) Math.pow(3, a) * 2;
        }
        // When the remainder is 0, do nothing
        return (int) Math.pow(3, a);
    }

max_product_cutting.cs

    /* Max product cutting: Greedy algorithm */
    int MaxProductCutting(int n) {
        // When n <= 3, must cut out a 1
        if (n <= 3) {
            return 1 * (n - 1);
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        int a = n / 3;
        int b = n % 3;
        if (b == 1) {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return (int)Math.Pow(3, a - 1) * 2 * 2;
        }
        if (b == 2) {
            // When the remainder is 2, do nothing
            return (int)Math.Pow(3, a) * 2;
        }
        // When the remainder is 0, do nothing
        return (int)Math.Pow(3, a);
    }

max_product_cutting.go

    /* Max product cutting: Greedy algorithm */
    func maxProductCutting(n int) int {
        // When n <= 3, must cut out a 1
        if n <= 3 {
            return 1 * (n - 1)
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        a := n / 3
        b := n % 3
        if b == 1 {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return int(math.Pow(3, float64(a-1))) * 2 * 2
        }
        if b == 2 {
            // When the remainder is 2, do nothing
            return int(math.Pow(3, float64(a))) * 2
        }
        // When the remainder is 0, do nothing
        return int(math.Pow(3, float64(a)))
    }

max_product_cutting.swift

    /* Max product cutting: Greedy algorithm */
    func maxProductCutting(n: Int) -> Int {
        // When n <= 3, must cut out a 1
        if n <= 3 {
            return 1 * (n - 1)
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        let a = n / 3
        let b = n % 3
        if b == 1 {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return pow(3, a - 1) * 2 * 2
        }
        if b == 2 {
            // When the remainder is 2, do nothing
            return pow(3, a) * 2
        }
        // When the remainder is 0, do nothing
        return pow(3, a)
    }

max_product_cutting.js

    /* Max product cutting: Greedy algorithm */
    function maxProductCutting(n) {
        // When n <= 3, must cut out a 1
        if (n <= 3) {
            return 1 * (n - 1);
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        let a = Math.floor(n / 3);
        let b = n % 3;
        if (b === 1) {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return Math.pow(3, a - 1) * 2 * 2;
        }
        if (b === 2) {
            // When the remainder is 2, do nothing
            return Math.pow(3, a) * 2;
        }
        // When the remainder is 0, do nothing
        return Math.pow(3, a);
    }

max_product_cutting.ts

    /* Max product cutting: Greedy algorithm */
    function maxProductCutting(n: number): number {
        // When n <= 3, must cut out a 1
        if (n <= 3) {
            return 1 * (n - 1);
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        let a: number = Math.floor(n / 3);
        let b: number = n % 3;
        if (b === 1) {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return Math.pow(3, a - 1) * 2 * 2;
        }
        if (b === 2) {
            // When the remainder is 2, do nothing
            return Math.pow(3, a) * 2;
        }
        // When the remainder is 0, do nothing
        return Math.pow(3, a);
    }

max_product_cutting.dart

    /* Max product cutting: Greedy algorithm */
    int maxProductCutting(int n) {
      // When n <= 3, must cut out a 1
      if (n <= 3) {
        return 1 * (n - 1);
      }
      // Greedily cut out 3, a is the number of 3s, b is the remainder
      int a = n ~/ 3;
      int b = n % 3;
      if (b == 1) {
        // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
        return (pow(3, a - 1) * 2 * 2).toInt();
      }
      if (b == 2) {
        // When the remainder is 2, do nothing
        return (pow(3, a) * 2).toInt();
      }
      // When the remainder is 0, do nothing
      return pow(3, a).toInt();
    }

max_product_cutting.rs

    /* Max product cutting: Greedy algorithm */
    fn max_product_cutting(n: i32) -> i32 {
        // When n <= 3, must cut out a 1
        if n <= 3 {
            return 1 * (n - 1);
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        let a = n / 3;
        let b = n % 3;
        if b == 1 {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            3_i32.pow(a as u32 - 1) * 2 * 2
        } else if b == 2 {
            // When the remainder is 2, do nothing
            3_i32.pow(a as u32) * 2
        } else {
            // When the remainder is 0, do nothing
            3_i32.pow(a as u32)
        }
    }

max_product_cutting.c

    /* Max product cutting: Greedy algorithm */
    int maxProductCutting(int n) {
        // When n <= 3, must cut out a 1
        if (n <= 3) {
            return 1 * (n - 1);
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        int a = n / 3;
        int b = n % 3;
        if (b == 1) {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return pow(3, a - 1) * 2 * 2;
        }
        if (b == 2) {
            // When the remainder is 2, do nothing
            return pow(3, a) * 2;
        }
        // When the remainder is 0, do nothing
        return pow(3, a);
    }

max_product_cutting.kt

    /* Max product cutting: Greedy algorithm */
    fun maxProductCutting(n: Int): Int {
        // When n <= 3, must cut out a 1
        if (n <= 3) {
            return 1 * (n - 1)
        }
        // Greedily cut out 3, a is the number of 3s, b is the remainder
        val a = n / 3
        val b = n % 3
        if (b == 1) {
            // When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
            return 3.0.pow((a - 1)).toInt() * 2 * 2
        }
        if (b == 2) {
            // When the remainder is 2, do nothing
            return 3.0.pow(a).toInt() * 2 * 2
        }
        // When the remainder is 0, do nothing
        return 3.0.pow(a).toInt()
    }

max_product_cutting.rb

    ### Maximum cutting product: greedy ###
    def max_product_cutting(n)
      # When n <= 3, must cut out a 1
      return 1 * (n - 1) if n <= 3
      # Greedily cut out 3, a is the number of 3s, b is the remainder
      a, b = n / 3, n % 3
      # When the remainder is 1, convert a pair of 1 * 3 to 2 * 2
      return (3.pow(a - 1) * 2 * 2).to_i if b == 1
      # When the remainder is 2, do nothing
      return (3.pow(a) * 2).to_i if b == 2
      # When the remainder is 0, do nothing
      3.pow(a).to_i
    end

Figure 15-16 Calculation method for max product cutting

The time complexity depends on how exponentiation is implemented in the programming language. Taking Python as an example, there are three commonly used ways to compute powers.

- Both the operator `**` and the function `pow()` have time complexity \(O(\log⁡ a)\).
- The function `math.pow()` internally calls the C library's `pow()` function, which performs floating-point exponentiation, with time complexity \(O(1)\).

Variables \(a\) and \(b\) use a constant amount of extra space, therefore the space complexity is \(O(1)\).

### 3. Correctness Proof

We use proof by contradiction and consider only the case where \(n \geq 4\).

1. All factors \(\leq 3\): Suppose the optimal splitting scheme includes a factor \(x \geq 4\). Then it can be further split into \(2(x-2)\) to obtain a larger (or equal) product. This contradicts the assumption.
2. The splitting scheme does not contain \(1\): Suppose the optimal splitting scheme includes a factor of \(1\). Then it can be merged into another factor to obtain a larger product. This contradicts the assumption.
3. The splitting scheme contains at most two \(2\)s: Suppose the optimal splitting scheme includes three \(2\)s. Then they can be replaced by two \(3\)s, yielding a larger product. This contradicts the assumption.

##### Feel free to drop your insights, questions or suggestions