Difficulty: 🟢 Easy
Topics: Array, Math

Solution

LeetCode 3512 - Minimum Operations to Make Array Sum Divisible by K

Problem Understanding

The problem gives us an integer array nums and an integer k.

We are allowed to repeatedly perform one operation: choose any index i and decrease nums[i] by exactly 1.

Our goal is to determine the minimum number of such operations needed so that the sum of all elements in the array becomes divisible by k.

A key observation is that every operation decreases the total array sum by exactly 1. The individual element chosen does not matter from the perspective of the total sum. Whether we subtract from one element many times or distribute the operations across multiple elements, each operation reduces the overall sum by one.

The input consists of:

nums, an array of positive integers.
k, the divisor that the final sum must be divisible by.

The output is a single integer representing the minimum number of decrement operations required.

The constraints are small:

nums.length <= 1000
nums[i] <= 1000
k <= 100

These constraints indicate that even simple approaches would run comfortably within limits. However, the mathematical structure of the problem allows for an extremely concise and efficient solution.

Several edge cases are important:

The sum may already be divisible by k, requiring zero operations.
The sum may be smaller than k.
The required number of operations could equal k - 1.
Reducing elements all the way to zero is allowed, as demonstrated in Example 3.
Since every element is initially positive and the total sum is at least as large as the remainder modulo k, there is always a valid way to perform the required decrements.

Approaches

Brute Force

A straightforward approach is to repeatedly decrease the sum by one until it becomes divisible by k.

We first compute the total sum. If the sum is not divisible by k, we perform one operation, reducing the sum by one, and check again. We continue until the sum becomes divisible by k.

This approach is correct because each operation reduces the sum by exactly one, and we stop at the first divisible value.

However, this method performs unnecessary simulation. If the remainder is large, we may execute many iterations just to discover how many decrements were needed.

Key Insight

Let:

$$S = \text{sum(nums)}$$

Suppose:

$$S \bmod k = r$$

Each operation decreases the sum by exactly one.

After x operations, the new sum becomes:

$$S - x$$

We need:

$$(S - x) \bmod k = 0$$

Since:

$$S \bmod k = r$$

the smallest nonnegative value of x satisfying the condition is exactly:

$$x = r$$

This is because subtracting the remainder removes the excess amount beyond the nearest lower multiple of k.

Therefore, the answer is simply:

$$\text{sum(nums)} \bmod k$$

No simulation is needed.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + r)	O(1)	Repeatedly decrement the sum until divisible
Optimal	O(n)	O(1)	Compute total sum and return its remainder modulo `k`

Where r = sum(nums) % k.

Algorithm Walkthrough

Compute the total sum of all elements in nums.
Compute the remainder when the sum is divided by k.
If the remainder is 0, the sum is already divisible by k, so return 0.
Otherwise, return the remainder itself.
This value represents the minimum number of decrement operations because every operation reduces the sum by exactly one.

Why it works

Let the total sum be S and let r = S % k.

By definition:

$$S = qk + r$$

for some integer q.

After exactly r decrement operations, the sum becomes:

$$S - r = qk$$

which is divisible by k.

Any smaller number of operations leaves a positive remainder, so the sum cannot yet be divisible by k. Therefore r is both sufficient and necessary, making it the minimum number of operations.

Problem Understanding

The problem defines a single global quantity, the sum of the array $S = \sum_{i=0}^{n-1} \text{nums}[i]$. We are allowed to perform an operation that selects any index $i$ and decrements $\text{nums}[i]$ by 1. Each such operation reduces the total sum $S$ by exactly 1.

The task is to determine the minimum number of such decrement operations required so that the resulting sum becomes divisible by $k$. In other words, we seek the smallest nonnegative integer $x$ such that

$$(S - x) \equiv 0 \pmod{k}.$$

Since each operation reduces the sum by exactly 1 and there is no restriction preventing repeated decrements on any element, the only state that matters is the total sum, not its distribution across the array.

The constraints $1 \leq \text{nums}[i] \leq 1000$, $1 \leq n \leq 1000$, and $1 \leq k \leq 100$ indicate that both computing the sum and performing modular arithmetic are trivial in scale. No overflow issues arise in typical 32-bit or 64-bit integer types if handled carefully in modern languages.

The primary edge cases are when the sum is already divisible by $k$, in which case zero operations are needed, and when $k = 1$, in which case every integer is divisible and the answer is always zero. Another implicit edge case is when the sum is smaller than $k$, where the remainder logic still applies correctly.

Approaches

The brute-force interpretation would attempt to simulate operations: repeatedly decrement elements in some order and track when the sum becomes divisible by $k$. However, this is unnecessary because each operation uniformly reduces the total sum regardless of which element is chosen. Thus, all that matters is how many times we subtract 1 from the total sum.

The key observation is that the final condition depends only on $S \bmod k$. If we want $S - x \equiv 0 \pmod{k}$, then we require $x \equiv S \pmod{k}$. The smallest nonnegative such $x$ is exactly $S \bmod k$.

This reduces the problem from a potentially combinatorial process over array elements to a single arithmetic computation.

Approach	Time Complexity	Space Complexity	Notes
Brute Force Simulation	$O(S)$	$O(1)$	Repeatedly decrement elements until divisible
Optimal Modular Reduction	$O(n)$	$O(1)$	Compute sum and return sum mod k

Algorithm Walkthrough

The optimal algorithm follows directly from the invariance of total sum reduction.

Compute the total sum $S$ of all elements in nums. This is justified because each operation reduces exactly one unit from this sum, independent of which index is chosen.
Compute the remainder $r = S \bmod k$. This step identifies how far $S$ is from the nearest lower multiple of $k$.
Return $r$ as the answer. This is valid because subtracting $r$ from $S$ produces $S - r$, which is divisible by $k$, and no smaller nonnegative subtraction can achieve divisibility.

Why it works

The process preserves a single invariant: the only reachable sums are of the form $S - x$ for $x \geq 0$. Among these, we seek the smallest $x$ such that $S - x \equiv 0 \pmod{k}$. Modular arithmetic guarantees that this occurs precisely when $x \equiv S \pmod{k}$, and the minimal such nonnegative representative is $S \bmod k$. Therefore the algorithm is both necessary and sufficient.

Python Solution

from typing import List

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return sum(nums) % k

The implementation directly follows the mathematical observation.

First, sum(nums) computes the total array sum. Then % k computes the remainder when dividing by k.

That remainder is exactly the number of decrements required to reach the nearest smaller multiple of k, so the method returns it immediately.

No loops beyond the summation are necessary, and no extra data structures are used. total_sum = sum(nums) return total_sum % k


The implementation first computes the sum of the array in linear time. This corresponds directly to computing $S$. It then returns $S \bmod k$, which represents the minimal number of unit decrements required to reach the nearest lower multiple of $k$.

No additional data structures are needed because the problem reduces entirely to a single scalar computation.

## Go Solution

```go
func minOperations(nums []int, k int) int {
    total := 0

    for _, num := range nums {
        total += num
    }

    return total % k
}

The Go solution is identical in logic to the Python version.

We accumulate the total sum using a range loop and then return total % k.

There are no special considerations regarding empty slices because the problem guarantees at least one element. Integer overflow is not a concern because the maximum possible sum is:

$$1000 \times 1000 = 1,000,000$$

which easily fits inside Go's int type. sum := 0 for _, v := range nums { sum += v } return sum % k }


The Go implementation mirrors the Python logic. It accumulates the sum in an integer variable and returns the remainder modulo $k$.

Unlike Python, Go uses fixed-width integer types depending on architecture, but given the constraints ($n \leq 1000$, $nums[i] \leq 1000$), overflow is not a concern. A 32-bit integer is sufficient.

## Worked Examples

### Example 1

**Input**

nums = [3, 9, 7] k = 5


Compute the sum:

| Step | Value |
| --- | --- |
| 3 + 9 + 7 | 19 |

Compute the remainder:

| Expression | Result |
| --- | --- |
| 19 % 5 | 4 |

Answer:


After four decrements, the sum becomes:

19 - 4 = 15


and `15` is divisible by `5`.

### Example 2

**Input**

nums = [4, 1, 3] k = 4


Compute the sum:

| Step | Value |
| --- | --- |
| 4 + 1 + 3 | 8 |

Compute the remainder:

| Expression | Result |
| --- | --- |
| 8 % 4 | 0 |

Answer:


The sum is already divisible by `4`.

### Example 3

**Input**

nums = [3, 2] k = 6


Compute the sum:

| Step | Value |
| --- | --- |
| 3 + 2 | 5 |

Compute the remainder:

| Expression | Result |
| --- | --- |
| 5 % 6 | 5 |

Answer:


After five decrement operations:

5 - 5 = 0


and `0` is divisible by `6`.
Input: `nums = [3, 9, 7], k = 5`

Compute sum:

$$S = 3 + 9 + 7 = 19$$

Compute remainder:

$$19 \bmod 5 = 4$$

Thus answer is 4.

State summary:

| Step | Value |
| --- | --- |
| Sum $S$ | 19 |
| $S \bmod k$ | 4 |
| Operations | 4 |

### Example 2

Input: `nums = [4, 1, 3], k = 4`

$$S = 8,\quad 8 \bmod 4 = 0$$

No operations are needed since the sum is already divisible.

### Example 3

Input: `nums = [3, 2], k = 6`

$$S = 5,\quad 5 \bmod 6 = 5$$

We must reduce the sum by 5 to reach 0, which is divisible by 6.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n) | Must scan the array once to compute the sum |
| Space | O(1) | Only a few integer variables are used |

The dominant operation is computing the sum of the array. After that, calculating the modulo is constant time. No auxiliary data structures proportional to input size are required.
| Time | $O(n)$ | One pass to compute the sum over $n$ elements |
| Space | $O(1)$ | Only a constant number of variables are used |

The computation is dominated by the linear traversal of the array. No auxiliary storage scales with input size.

## Test Cases

sol = Solution()

assert sol.minOperations([3, 9, 7], 5) == 4 # Example 1 assert sol.minOperations([4, 1, 3], 4) == 0 # Example 2 assert sol.minOperations([3, 2], 6) == 5 # Example 3

assert sol.minOperations([1], 1) == 0 # Smallest possible input assert sol.minOperations([1], 2) == 1 # Single decrement needed assert sol.minOperations([1000], 100) == 0 # Already divisible assert sol.minOperations([999], 100) == 99 # Large remainder

assert sol.minOperations([1, 1, 1], 2) == 1 # Odd sum, divisor 2 assert sol.minOperations([1, 1, 1, 1], 2) == 0 # Even sum, divisor 2

assert sol.minOperations([5, 5, 5], 7) == 1 # Sum 15, remainder 1 assert sol.minOperations([10, 20, 30], 7) == 4 # General case

assert sol.minOperations([1000] * 1000, 100) == 0 # Maximum-sized divisible case


### Test Summary

| Test | Why |
| --- | --- |
| `[3,9,7], k=5` | Verifies Example 1 |
| `[4,1,3], k=4` | Verifies already divisible case |
| `[3,2], k=6` | Verifies Example 3 |
| `[1], k=1` | Smallest valid input |
| `[1], k=2` | Single element requiring one operation |
| `[1000], k=100` | Large value already divisible |
| `[999], k=100` | Large remainder case |
| `[1,1,1], k=2` | Odd sum with divisor 2 |
| `[1,1,1,1], k=2` | Even sum with divisor 2 |
| `[5,5,5], k=7` | Small nonzero remainder |
| `[10,20,30], k=7` | Typical arbitrary input |
| `[1000] * 1000, k=100` | Maximum constraint stress test |

## Edge Cases

### Sum Already Divisible by K

If `sum(nums) % k == 0`, no operations are necessary. A common mistake is to subtract an entire multiple of `k` or perform unnecessary work. The implementation correctly returns `0` immediately because the remainder is zero.

### Sum Smaller Than K

When the total sum is less than `k`, the remainder is simply the sum itself. For example, if `sum(nums) = 5` and `k = 6`, the answer is `5`. The modulo operation naturally handles this situation without any special logic.

### Maximum Possible Remainder

The largest answer occurs when the remainder equals `k - 1`. For example, if the sum is `999` and `k = 100`, then:

$$999 \bmod 100 = 99$$

The implementation returns `99`, which is exactly the number of decrements required to reach `900`.

### Single Element Arrays

When the array contains only one element, all operations must be applied to that element. Since the solution depends only on the total sum and not on how decrements are distributed, the same formula remains valid and requires no special handling.

### Large Inputs

The maximum array length is `1000`, and each element can be as large as `1000`. Computing the sum requires only a single pass through the array, so the solution remains efficient even at the largest allowed input size.
assert Solution().minOperations([3, 9, 7], 5) == 4  # provided example 1
assert Solution().minOperations([4, 1, 3], 4) == 0  # already divisible
assert Solution().minOperations([3, 2], 6) == 5     # must reduce to 0
assert Solution().minOperations([1], 1) == 0        # k = 1 edge case
assert Solution().minOperations([10], 3) == 1       # single element remainder
assert Solution().minOperations([1]*1000, 100) == (1000 % 100)  # large n

Test	Why
`[3,9,7],5`	verifies general correctness
`[4,1,3],4`	already divisible sum
`[3,2],6`	sum smaller than k
`[1],1`	k = 1 edge case
`[10],3`	simple modular reduction
large array	performance and accumulation correctness

Edge Cases

One important edge case is when the sum is already divisible by $k$. In this case, $S \bmod k = 0$, and the algorithm correctly returns zero without performing any operations.

Another edge case occurs when $k = 1$. Since every integer is divisible by 1, the correct answer is always zero. The modulo computation naturally yields zero because any integer modulo 1 is zero.

A third edge case is when the array contains a single element. The logic still holds because the sum is just that element, and the answer reduces to a simple modular computation. This ensures the algorithm does not rely on array size assumptions and remains valid in degenerate cases.