Problem

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

1
2
3
4
5

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

1
2
3
4

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

1
2
3
4
5

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

Examples

Solution

Method 1 – Math & Greedy

Intuition

To make the sum divisible by k, we need to reduce the sum by its remainder modulo k. The minimum number of operations is equal to the remainder, and we can perform all operations on any element as long as it is large enough.

Approach

  1. Calculate the sum of nums.
  2. Compute remainder = sum % k.
  3. If remainder == 0, answer is 0.
  4. Otherwise, answer is remainder.
  5. Edge case: If all elements are smaller than remainder, we need to distribute operations among multiple elements.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int rem = sum % k;
        return rem == 0 ? 0 : rem;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func minOperations(nums []int, k int) int {
    sum := 0
    for _, v := range nums {
        sum += v
    }
    rem := sum % k
    if rem == 0 {
        return 0
    }
    return rem
}
1
2
3
4
5
6
7
8

class Solution {
    public int minOperations(int[] nums, int k) {
        int sum = 0;
        for (int v : nums) sum += v;
        int rem = sum % k;
        return rem == 0 ? 0 : rem;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun minOperations(nums: IntArray, k: Int): Int {
        val sum = nums.sum()
        val rem = sum % k
        return if (rem == 0) 0 else rem
    }
}
1
2
3
4

class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        rem: int = sum(nums) % k
        return 0 if rem == 0 else rem
1
2
3
4
5
6
7

impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        let sum: i32 = nums.iter().sum();
        let rem = sum % k;
        if rem == 0 { 0 } else { rem }
    }
}
1
2
3
4
5
6

class Solution {
    minOperations(nums: number[], k: number): number {
        const rem = nums.reduce((a, b) => a + b, 0) % k;
        return rem === 0 ? 0 : rem;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once to compute the sum.
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.

Solution

Method 1 – Math & Greedy

Intuition

To make the sum divisible by k, we need to reduce the sum by its remainder modulo k. The minimum number of operations is equal to the remainder, and we can perform all operations on any element as long as it is large enough.

Approach

  1. Calculate the sum of nums.
  2. Compute remainder = sum % k.
  3. If remainder == 0, answer is 0.
  4. Otherwise, answer is remainder.
  5. Edge case: If all elements are smaller than remainder, we need to distribute operations among multiple elements.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        int rem = sum % k;
        return rem == 0 ? 0 : rem;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

func minOperations(nums []int, k int) int {
    sum := 0
    for _, v := range nums {
        sum += v
    }
    rem := sum % k
    if rem == 0 {
        return 0
    }
    return rem
}
1
2
3
4
5
6
7
8

class Solution {
    public int minOperations(int[] nums, int k) {
        int sum = 0;
        for (int v : nums) sum += v;
        int rem = sum % k;
        return rem == 0 ? 0 : rem;
    }
}
1
2
3
4
5
6
7

class Solution {
    fun minOperations(nums: IntArray, k: Int): Int {
        val sum = nums.sum()
        val rem = sum % k
        return if (rem == 0) 0 else rem
    }
}
1
2
3
4

class Solution:
    def minOperations(self, nums: list[int], k: int) -> int:
        rem = sum(nums) % k
        return 0 if rem == 0 else rem
1
2
3
4
5
6
7

impl Solution {
    pub fn min_operations(nums: Vec<i32>, k: i32) -> i32 {
        let sum: i32 = nums.iter().sum();
        let rem = sum % k;
        if rem == 0 { 0 } else { rem }
    }
}
1
2
3
4
5
6

class Solution {
    minOperations(nums: number[], k: number): number {
        const rem = nums.reduce((a, b) => a + b, 0) % k;
        return rem === 0 ? 0 : rem;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once to compute the sum.
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.