14. 数组元素之和最小化

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐⭐⭐ 中

问题描述

小 C 希望构造一个包含 n 个元素的数组，且满足以下条件：

1. 数组中的所有元素两两不同。
2. 数组所有元素的最大公约数为 k。
3. 数组元素之和尽可能小。

任务是输出该数组元素之和的最小值。

测试样例

样例 1：

输入：n = 3 ,k = 1
输出：6

样例 2：

输入：n = 2 ,k = 2
输出：6

样例 3：

输入：n = 4 ,k = 3
输出：30

解题思路

要解决这个问题，我们需要构造一个满足以下条件的数组：

1. 所有元素两两不同。
2. 所有元素的最大公约数（GCD）为 k。
3. 数组元素之和尽可能小。

关键观察：

1. GCD 为 k：这意味着所有元素都必须是 k 的倍数。因此，我们可以将问题转化为构造一个数组，其中每个元素除以 k 后，这些新元素的最大公约数为 1。
2. 元素两两不同：为了确保元素不同，我们可以选择最小的 n 个不同的正整数，然后将它们乘以 k。
3. 和最小：为了使和最小，我们应该选择最小的 n 个不同的正整数，即 1, 2, 3, ..., n，然后将它们乘以 k。这样，数组的和就是 k * (1 + 2 + ... + n) = k * n * (n + 1) / 2。

验证：

• 对于样例 1：n = 3, k = 1，和为 1 * (1 + 2 + 3) = 6，与输出一致。
• 对于样例 2：n = 2, k = 2，和为 2 * (1 + 2) = 6，与输出一致。
• 对于样例 3：n = 4, k = 3，和为 3 * (1 + 2 + 3 + 4) = 30，与输出一致。

代码实现

function solution(n, k) {
    // 计算前 n 个正整数的和，然后乘以 k
    return k * n * (n + 1) / 2;
}

function main() {
    console.log(solution(3, 1) === 6); // true
    console.log(solution(2, 2) === 6); // true
    console.log(solution(4, 3) === 30); // true
}

main();

代码解释：

1. **solution(n, k)**：计算前 n 个正整数的和（即 n * (n + 1) / 2），然后乘以 k，得到满足条件的最小和。
2. **main()**：测试函数，验证三个样例的输出是否正确。

这个解法的时间复杂度是 O(1)，空间复杂度也是 O(1)，是最优的。

以上关于14. 数组元素之和最小化的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。