How do I solve the Minimum Operations to Make Array Sum Divisible by K?

To solve this, you need to calculate the remainder of the sum of the array when divided by k. Then find the minimum adjustments required to make the sum divisible by k.

What is the best approach for solving this problem?

The best approach is to first calculate the sum of the array, then find the remainder when divided by k, and adjust the sum using the least number of operations to make it divisible by k.

How does the modulo operation help in this problem?

The modulo operation helps in determining the remainder of the sum when divided by k, which is key to finding out how much needs to be added or subtracted to achieve divisibility.

What if the sum is already divisible by k?

If the sum is already divisible by k, then no operations are needed, and the answer is zero.

Can this problem be solved using dynamic programming?

While dynamic programming could be applied to some variants of the problem, a direct approach using modular arithmetic and greedy adjustments is typically the most efficient.

#3512

Easy

auto_awesome数组·数学

LeetCode 题解工作台

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

给你一个整数数组 nums 和一个整数 k 。你可以执行以下操作任意次：选择一个下标 i ，并将 nums[i] 替换为 nums[i] - 1 。返回使数组元素之和能被 k 整除所需的最小操作次数。示例 1：输入： nums = [3,9,7], k = 5 输出： 4 解释：对 n…

数组数学

题目描述

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

lightbulb

解题思路

方法一：求和取模

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

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

1

2

3

4

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Tests understanding of modulo and array manipulation.
question_mark
Evaluates ability to work with array sums and math-based optimizations.
question_mark
Assesses problem-solving skills in handling operations within constraints.

warning

常见陷阱

外企场景

error
Forgetting to account for the case where the sum is already divisible by k (requires zero operations).
error
Overcomplicating the problem by trying to use more than one operation per element.
error
Not correctly adjusting the sum by the minimum necessary amount, leading to incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if we allowed negative numbers in the array?
arrow_right_alt
What if the array elements were limited to powers of two?
arrow_right_alt
What if we needed to make the sum divisible by a prime number instead of k?

help

常见问题

外企场景

继续练习

#3513 不同 XOR 三元组的数目 I #3514 不同 XOR 三元组的数目 II #3505 使 K 个子数组内元素相等的最少操作数