跳转至

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

题目描述

给你一个整数数组 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

解法

方法一：求和取模

题目实际上是求数组元素之和对 \(k\) 取模的结果。因此，我们只需要遍历数组，计算出所有元素之和，然后对 \(k\) 取模，最后返回这个结果即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。空间复杂度 \(O(1)\)。

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

1
2
3
4
5
class Solution {
    public int minOperations(int[] nums, int k) {
        return Arrays.stream(nums).sum() % k;
    }
}

1
2
3
4
5
6
class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        return reduce(nums.begin(), nums.end(), 0) % k;
    }
};

1
2
3
4
5
6
func minOperations(nums []int, k int) (ans int) {
    for _, x := range nums {
        ans = (ans + x) % k
    }
    return
}

1
2
3
function minOperations(nums: number[], k: number): number {
    return nums.reduce((acc, x) => acc + x, 0) % k;
}

评论