Minimum Operations to Make Array Sum Divisible by K

EASY

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

Approaches

Checkout 2 different approaches to solve Minimum Operations to Make Array Sum Divisible by K. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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.

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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a constant amount of extra space for variables like sum and the loop counter.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Minimum Operations to Make Array Sum Divisible by K. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Minimum Operations to Make Array Sum Divisible by K

Patterns:

Math

Data Structures:

Array

Minimum Operations to Make Array Sum Divisible by K

Description

Approaches

Brute Force Iteration

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Patterns:

Data Structures:

On this page

Subscribe to Scale Engineer newsletter