Minimum Operations to Make Array Sum Divisible by K
EasyPrompt
You are given an integer array nums and an integer k. You can perform the following operation any number of times:
- Select an index
iand replacenums[i]withnums[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] = 3and 2 operations onnums[1] = 2. Now,nums = [0, 0]. - The sum is 0, which is divisible by 6.
Constraints:
1 <= nums.length <= 10001 <= nums[i] <= 10001 <= 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
Sof all elements in thenumsarray. - Iterate with a variable
opsfrom 0 up toS. - In each iteration, calculate the potential new sum
newSum = S - ops. - Check if
newSumis divisible byk(i.e.,newSum % k == 0). - If it is,
opsis the minimum number of operations. Returnopsand 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.
This highly efficient approach uses modular arithmetic to find the answer directly, without any iteration or simulation. It's based on the insight that the total reduction needed is determined by the remainder of the initial sum when divided by k.
Algorithm
- Calculate the total sum
Sof all elements in thenumsarray. - Compute the remainder of
Swhen divided byk. Let this berem = S % k. - This remainder
remis the minimum number of operations required. Returnrem.
Walkthrough
Let the initial sum of the array be S. The goal is to find the minimum number of operations, ops, such that the new sum S' = S - ops is divisible by k. This can be written as:
(S - ops) % k == 0
Using the properties of modular arithmetic, this is equivalent to:
S % k ≡ ops % k
Let rem = S % k. The equation becomes rem ≡ ops % k. We are looking for the smallest non-negative integer ops that satisfies this condition. The smallest such value is simply rem itself.
For example, if S = 19 and k = 5, then rem = 19 % 5 = 4. We need ops % 5 = 4. The smallest non-negative ops is 4.
This number of operations is always achievable because the total sum S is always greater than or equal to its remainder rem when divided by k. Therefore, we can always perform rem decrements on the array elements to reduce the sum by rem.
class Solution { public int minOperations(int[] nums, int k) { long sum = 0; for (int num : nums) { sum += num; } return (int) (sum % k); }}Complexity
Time
O(N), where N is the length of the array. This is for the single pass to compute the sum.
Space
O(1), as it uses only a constant amount of extra space.
Trade-offs
Pros
Extremely efficient, with linear time complexity.
Provides a direct solution without unnecessary computations.
Code is very simple and concise.
Cons
Requires a basic understanding of modular arithmetic to derive the solution.
Solutions
Solution
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; }};class Solution: def minOperations(self, nums: List[int], k: int) -> int: return sum(nums) % kVideo 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.