Skip to content

3958. Minimum Cost to Split into Ones II πŸ”’

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 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

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

 

Constraints:

  • 1 <= n <= 5 * 107

Solutions

Solution 1: Mathematics

Thinking

\(n\) reaches \(5\times 10^7\), so any step-by-step splitting is too slow. Splitting \(x\) into \(1\) and \(x-1\) costs \(x-1\); repeating down to all ones sums \(1+2+\cdots+(n-1)\).

That strategy is the closed form \(\dfrac{n(n-1)}{2}\). More balanced splits do not help: every final \(1\) still pays a neighboring difference, and the total is unchanged.

Return the formula in \(O(1)\).

To minimize the cost, we should first split \(n\) into \(1\) and \(n - 1\), which costs \(n - 1\); then split \(n - 1\) into \(1\) and \(n - 2\), which costs \(n - 2\). Following this pattern, the total cost is accumulated as \(1 + 2 + \dots + (n - 1) = \frac{n \times (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 long minCost(int n) {
        return 1L * n * (n - 1) / 2;
    }
}

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

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

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

Comments