3958. Minimum Cost to Split into Ones II 🔒

题目描述

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:

Example 2:

Constraints:

• 1 <= n <= 5 * 107

解法

方法一：数学

要使得成本最小，我们应该首先将 \(n\) 拆分成 \(1\) 和 \(n - 1\)，所需成本为 \(n - 1\)；然后将 \(n - 1\) 拆分成 \(1\) 和 \(n - 2\)，所需成本为 \(n - 2\)。依此类推，得到总成本为 \(1 + 2 + \dots + (n - 1) = \frac{n \times (n - 1)}{2}\)。

时间复杂度 \(O(1)\)，空间复杂度 \(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;
}

评论