Skip to content

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

Thinking

Each operation decreases one element by \(1\), hence the total sum by \(1\). The sum is divisible by \(k\) after exactly \(S \bmod k\) operations.

A single pass that sums and reduces modulo \(k\) is enough; there is no need to simulate each decrement.

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)\).

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;
}

1
2
3
4
5
impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        nums.iter().sum::<i32>() % k
    }
}

1
2
3
4
5
public class Solution {
    public int MinOperations(int[] nums, int k) {
        return nums.Sum() % k;
    }
}

Comments