Scale Engineer

Minimum Operations to Make Array Sum Divisible by K

Easy
#3124Time: O(N + S), where N is the length of the array and S is the sum of its elements. Calculating the sum takes O(N) time. The loop can run up to S times in the worst case.Space: O(1), as we only use a constant amount of extra space for variables like sum and the loop counter.
Patterns
Math
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the problem by testing each possible number of operations, starting from zero. It iteratively checks if reducing the total sum by a certain number of operations makes it divisible by k.

Algorithm

  • Calculate the initial sum S of all elements in the nums array.
  • Iterate with a variable ops from 0 up to S.
  • In each iteration, calculate the potential new sum newSum = S - ops.
  • Check if newSum is divisible by k (i.e., newSum % k == 0).
  • If it is, ops is the minimum number of operations. Return ops and terminate.

Walkthrough

The core idea is to find the smallest non-negative integer ops such that (sum(nums) - ops) is divisible by k. We can achieve this by starting with ops = 0 and incrementing it, checking the divisibility condition at each step. The first ops that satisfies the condition is guaranteed to be the minimum.

For example, if the sum is 19 and k is 5, we check:

  • ops = 0: (19 - 0) % 5 = 4 (not divisible)
  • ops = 1: (19 - 1) % 5 = 3 (not divisible)
  • ops = 2: (19 - 2) % 5 = 2 (not divisible)
  • ops = 3: (19 - 3) % 5 = 1 (not divisible)
  • ops = 4: (19 - 4) % 5 = 0 (divisible). So, the minimum operations is 4.

This process is guaranteed to terminate because, in the worst case, we can perform sum(nums) operations to make the sum 0, which is divisible by any k.

class Solution {    public int minOperations(int[] nums, int k) {        long sum = 0;        for (int num : nums) {            sum += num;        }         for (int ops = 0; ops <= sum; ops++) {            if ((sum - ops) % k == 0) {                return ops;            }        }                return 0; // This line is unreachable given the problem constraints.    }}

Complexity

Time

O(N + S), where N is the length of the array and S is the sum of its elements. Calculating the sum takes O(N) time. The loop can run up to S times in the worst case.

Space

O(1), as we only use a constant amount of extra space for variables like sum and the loop counter.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Directly follows the problem's definition of finding the smallest number of operations.

Cons

  • Inefficient for large sums. The runtime depends on the magnitude of the input values, not just the array size.

  • Performs many unnecessary checks compared to a direct mathematical solution.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem