3512. 使数组总和能被 K 整除的最小操作次数

Easy

题目描述

给你一个整数数组 nums 和一个整数 k。你可以执行以下操作任意次数：

• 选择一个下标 i，将 nums[i] 替换为 nums[i] - 1。

返回使数组总和能被 k 整除所需的最小操作次数。

示例 1：

输入：nums = [3,9,7], k = 5
输出：4
解释：
对 nums[1] = 9 执行 4 次操作。现在，nums = [3, 5, 7]。
总和是 15，能被 5 整除。

示例 2：

输入：nums = [4,1,3], k = 4
输出：0
解释：
总和是 8，已经能被 4 整除。因此，不需要任何操作。

示例 3：

输入：nums = [3,2], k = 6
输出：5
解释：
对 nums[0] = 3 执行 3 次操作，对 nums[1] = 2 执行 2 次操作。现在，nums = [0, 0]。
总和是 0，能被 6 整除。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• 1 <= k <= 100

提示：sum(nums) % k

解题思路

解题思路

这道题的关键在于理解题目要求：我们只能对数组元素执行减 1 操作，目标是使数组总和能被 k 整除。

首先，我们需要分析当前数组总和与 k 的关系：

• 如果 sum % k == 0，说明已经能被整除，无需操作
• 如果 sum % k != 0，我们需要减少数组总和使其能被 k 整除

设当前总和为 sum，余数为 remainder = sum % k。为了使总和能被 k 整除，我们需要减少 remainder 的值。

关键观察：由于我们只能执行减 1 操作，最直接的方法是减少总和直到它能被 k 整除。但是，我们还需要考虑一个重要的约束条件 - 数组中的每个元素都不能变成负数。

更深入的分析：

• 我们需要减少的总量就是 remainder = sum % k
• 如果 remainder == 0，无需操作
• 否则，我们需要执行 remainder 次减 1 操作

由于题目保证了解的存在性（从示例3可以看出，最坏情况下可以把所有元素减到0），我们只需要返回余数值即可。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return sum % k;
    }
};

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return sum(nums) % k

public class Solution {
    public int MinOperations(int[] nums, int k) {
        int sum = 0;
        foreach (int num in nums) {
            sum += num;
        }
        return sum % k;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperations = function(nums, k) {
    let sum = nums.reduce((acc, num) => acc + num, 0);
    return sum % k;
};

复杂度分析