Skip to content

3857. Minimum Cost to Split into Ones

Description

You are given an integer n.

In one operation, you may split an integer x into two positive integers a and b such that a + b = x.

The cost of this operation is a * b.

Return an integer denoting the minimum total cost required to split the integer n into n ones.

 

Example 1:

Input: n = 3

Output: 3

Explanation:

One optimal set of operations is:

x a b a + b a * b Cost
3 1 2 3 2 2
2 1 1 2 1 1

Thus, the minimum total cost is 2 + 1 = 3.

Example 2:

Input: n = 4

Output: 6

Explanation:

One optimal set of operations is:

x a b a + b a * b Cost
4 2 2 4 4 4
2 1 1 2 1 1
2 1 1 2 1 1

Thus, the minimum total cost is 4 + 1 + 1 = 6.

 

Constraints:

  • 1 <= n <= 500

Solutions

Solution 1: Math

Thinking

Split \(n\) into \(a+b=n\) at cost \(a \cdot b\) until everything is \(1\), minimizing total cost. \(n \le 500\) allows DP, but the optimum is closed-form.

The product \(a(n-a)\) is minimized at \(a=1\). Always peel off a \(1\), leaving \(n-1,n-2,\ldots,2\).

The total is \(1+2+\cdots+(n-1)=n(n-1)/2\).

Other splits need not be searched.

To minimize the total cost, we first split \(n\) into \(1\) and \(n-1\), with a cost of \(1 \cdot (n-1) = n-1\). Next, we split \(n-1\) into \(1\) and \(n-2\), with a cost of \(1 \cdot (n-2) = n-2\).

We continue this process until we split \(2\) into \(1\) and \(1\), with a cost of \(1 \cdot 1 = 1\). Therefore, the total cost is \((n-1) + (n-2) + \ldots + 2 + 1 = \frac{n(n-1)}{2}\).

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
class Solution:
    def minCost(self, n: int) -> int:
        return n * (n - 1) // 2

1
2
3
4
5
class Solution {
    public int minCost(int n) {
        return n * (n - 1) / 2;
    }
}

1
2
3
4
5
6
class Solution {
public:
    int minCost(int n) {
        return n * (n - 1) / 2;
    }
};

1
2
3
func minCost(n int) int {
    return n * (n - 1) / 2
}

1
2
3
function minCost(n: number): number {
    return (n * (n - 1)) >> 1;
}

Comments