Cut rope to maximise product

Problem Overview

To maximise the product of positive integer piece lengths that sum to n, greedy works: 3 is the optimal chunk size.

Intuition

To maximise the product of positive integer piece lengths that sum to n, greedy works: 3 is the optimal chunk size. Use as many 3s as possible. The only awkward remainder is 1 — then borrow one 3 and make a 4 instead (2+2 beats 3+1). For n = 2 or n = 3, the answer is n - 1. Compute 3^count with fast exponentiation and multiply by 2 or 4 when a leftover remainder remains.

Algorithm

1If n is 2 or 3, return n - 1.
2Set cnt3 = n / 3 and rem = n % 3.
3If rem == 1, decrement cnt3 and set rem = 4 (use one 4 instead of 3+1).
4Compute product = 3^cnt3 using binary exponentiation.
5If rem is 2 or 4, multiply product by rem.
6Return product.

Example Walkthrough

Input: n = 10

1. n / 3 → cnt3 = 3, rem = 1.
2. rem == 1 → cnt3 = 2, rem = 4.
3. 3^2 = 9; multiply by 4 → 36.
4. Pieces 3 + 3 + 4 sum to 10; product 36 beats 3+3+3+1 = 27.

Output: 36

Common Pitfalls

• Remainder 1 needs cnt3-- and rem = 4 — do not leave a lone 1 segment.
• Base cases n = 2 and n = 3 return n - 1, not 1.
• Use long or BigInteger if n is large enough to overflow int product.

Cut rope to maximise product.java

Java


// Approach: To maximise the product of rope pieces, use as many length-3 segments as possible (greedy).
// If the remainder after dividing by 3 is 1, replace one 3 with 4 (e.g. length 4 = 2+2 beats 3+1).
// Handle n = 2 or n = 3 as base cases (return n - 1).
// Multiply 3^cnt3 with binary exponentiation; if remainder is 2 or 4, multiply that factor in.
// Time: O(log n) Space: O(1)
class Solution {

    public int maxProduct(int n) {
        if (n == 2 || n == 3) {
            return n - 1;
        }

        int cnt3 = n / 3;
        int rem = n % 3;

        if (rem == 1) {
            cnt3 -= 1;
            rem = 4;
        }

        int prd = power(3, cnt3);
        if (rem == 2 || rem == 4) {
            prd *= rem;
        }

        return prd;
    }

    private int power(int base, int exp) {
        int res = 1;

        while (exp > 0) {
            if ((exp & 1) != 0) {
                res *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return res;
    }
}

Was this solution helpful?