Minimum Operations to Make Array Sum Divisible by K - Solution & Explanation

Problem Overview: You are given an integer array and a number k. Each operation increases the total array sum by 1. The goal is to determine the minimum number of operations required so the final sum becomes divisible by k.

Approach 1: Increment Simulation (Brute Force) (Time: O(n + k), Space: O(1))

Start by computing the total array sum using a single pass through the array. If the sum is already divisible by k, the answer is 0. Otherwise, repeatedly simulate operations by incrementing the sum until sum % k == 0. Each increment represents one operation. In the worst case, you may need up to k-1 increments before the remainder reaches zero. This approach is easy to reason about and mirrors the problem statement directly, but the repeated increments are unnecessary once you realize the pattern in modular arithmetic. The array traversal is O(n), and the simulation loop adds up to O(k) steps.

Approach 2: Sum and Modulo (Optimal) (Time: O(n), Space: O(1))

The key observation comes from modular arithmetic. Let S be the array sum. If S % k = r, then the sum needs k - r additional increments to reach the next multiple of k. If the remainder is already zero, no operations are needed. This leads directly to the formula (k - (S % k)) % k. The extra modulo ensures the result becomes zero when the sum is already divisible. Implementation is straightforward: iterate through the array once to compute the sum, calculate the remainder with k, and return the required difference. The algorithm runs in linear time with constant space and avoids unnecessary iteration.

This technique relies on simple arithmetic properties and is common in problems involving divisibility and modular adjustments. Many array problems reduce to computing aggregates like sums or counts before applying a mathematical rule. Understanding how remainders behave under addition makes this pattern easy to reuse across similar math and array problems.

Recommended for interviews: The Sum and Modulo approach is what interviewers expect. Mentioning the brute force simulation first demonstrates understanding of the problem mechanics, but deriving the direct formula using modular arithmetic shows stronger problem-solving skills and leads to the optimal O(n) time and O(1) space solution.