3512. Minimum Operations to Make Array Sum Divisible by K

Description

You are given an integer array nums and an integer k. You can perform the following operation any number of times:

• Select an index i and replace nums[i] with nums[i] - 1.

Return the minimum number of operations required to make the sum of the array divisible by k.

 

Example 1:

Input: nums = [3,9,7], k = 5

Output: 4

Explanation:

• Perform 4 operations on nums[1] = 9. Now, nums = [3, 5, 7].
• The sum is 15, which is divisible by 5.

Example 2:

Input: nums = [4,1,3], k = 4

Output: 0

Explanation:

• The sum is 8, which is already divisible by 4. Hence, no operations are needed.

Example 3:

Input: nums = [3,2], k = 6

Output: 5

Explanation:

• Perform 3 operations on nums[0] = 3 and 2 operations on nums[1] = 2. Now, nums = [0, 0].
• The sum is 0, which is divisible by 6.

 

Constraints:

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

Solutions

Solution 1: Sum and Modulo

The problem essentially asks for the result of the sum of the array elements modulo \(k\). Therefore, we only need to iterate through the array, calculate the sum of all elements, and then take the modulo \(k\). Finally, return this result.

The time complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

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

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

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

func minOperations(nums []int, k int) (ans int) {
    for _, x := range nums {
        ans = (ans + x) % k
    }
    return
}

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

Comments