# Minimum Operations to Make Array Sum Divisible by K
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-operations-to-make-array-sum-divisible-by-k)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-array-sum-divisible-by-k
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
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
## 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`.
**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.
**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.
### Explanation
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`.

```java
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.
    }
}
```
### 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.

## Optimal Mathematical Approach
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`.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public int minOperations(int[] nums, int k) {
        long sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return (int) (sum % k);
    }
}
```
### Algorithm
- Calculate the total sum `S` of all elements in the `nums` array.
- Compute the remainder of `S` when divided by `k`. Let this be `rem = S % k`.
- This remainder `rem` is the minimum number of operations required. Return `rem`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  int minOperations(vector<int> &nums, int k) {
    return reduce(nums.begin(), nums.end(), 0) % k;
  }
};

```

### Python

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

```