# Make Sum Divisible by P
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/make-sum-divisible-by-p)
Canonical: https://scaleengineer.com/dsa/problems/make-sum-divisible-by-p
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung), [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## Problem
Given an array of positive integers `nums`, remove the **smallest** subarray (possibly **empty**) such that the **sum** of the remaining elements is divisible by `p`. It is **not** allowed to remove the whole array.

Return _the length of the smallest subarray that you need to remove, or_ `-1` _if it's impossible_.

A **subarray** is defined as a contiguous block of elements in the array.

**Example 1:**

**Input:** nums = [3,1,4,2], p = 6
**Output:** 1
**Explanation:** The sum of the elements in nums is 10, which is not divisible by 6. We can remove the subarray [4], and the sum of the remaining elements is 6, which is divisible by 6.

**Example 2:**

**Input:** nums = [6,3,5,2], p = 9
**Output:** 2
**Explanation:** We cannot remove a single element to get a sum divisible by 9. The best way is to remove the subarray [5,2], leaving us with [6,3] with sum 9.

**Example 3:**

**Input:** nums = [1,2,3], p = 3
**Output:** 0
**Explanation:** Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

**Constraints:**

* `1 <= nums.length <= 105`
* `1 <= nums[i] <= 109`
* `1 <= p <= 109`

# Approaches
## Brute Force Approach
This approach systematically checks every possible contiguous subarray within the given array `nums`. For each subarray, it calculates its sum and checks if this sum's remainder when divided by `p` is the one we need to make the total sum divisible by `p`. To avoid a cubic time complexity, the sum of the subarray is calculated incrementally in the inner loop.
**Time:** O(N^2), where N is the number of elements in `nums`. The nested loops result in a quadratic number of operations as we consider every possible subarray. · **Space:** O(1), as we only use a few variables to store the sums and the minimum length, regardless of the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space.
**Cons:** The O(N^2) time complexity is too slow for the given constraints (N up to 10^5) and will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
First, we need to figure out what property the sum of the removed subarray must have. Let the total sum of `nums` be `S` and the sum of the subarray to be removed be `S_sub`. We want the sum of the remaining elements, `S - S_sub`, to be divisible by `p`. In terms of modular arithmetic, this means `(S - S_sub) % p == 0`, which simplifies to `S % p == S_sub % p`. 

So, the problem reduces to finding the shortest subarray whose sum modulo `p` is equal to the total sum modulo `p`. Let's call this required remainder `target_rem`. If `target_rem` is already 0, we don't need to remove anything, and the answer is 0.

Otherwise, we can iterate through all possible starting positions `i` and ending positions `j` of a subarray. For each subarray, we compute its sum and check if its remainder modulo `p` equals `target_rem`. We keep track of the minimum length of such a subarray found so far. If, after checking all subarrays, the minimum length found is still the length of the entire array, it's impossible to solve by removing a *proper* subarray, so we return -1.

```java
class Solution {
    public int minSubarray(int[] nums, int p) {
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int targetRem = (int)(totalSum % p);
        if (targetRem == 0) {
            return 0;
        }

        int n = nums.length;
        int minLength = n;

        for (int i = 0; i < n; i++) {
            long currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += nums[j];
                if (currentSum % p == targetRem) {
                    minLength = Math.min(minLength, j - i + 1);
                }
            }
        }

        return minLength == n ? -1 : minLength;
    }
}
```
### Algorithm
1. Calculate the total sum of all elements in `nums`. Let's call it `totalSum`.
2. Determine the required remainder of the subarray to be removed. This is `target_rem = totalSum % p`.
3. If `target_rem` is 0, the array sum is already divisible by `p`. No removal is needed, so return 0.
4. Initialize a variable `minLength` to `n` (the length of the array), which will store the length of the smallest valid subarray found.
5. Use nested loops to iterate through all possible subarrays. The outer loop `i` runs from `0` to `n-1` (start index), and the inner loop `j` runs from `i` to `n-1` (end index).
6. For each starting index `i`, maintain a `currentSum` for the subarray starting at `i`. As `j` increments, add `nums[j]` to `currentSum`.
7. In the inner loop, check if `currentSum % p == target_rem`. 
8. If the condition is met, it means removing the subarray `nums[i...j]` would make the remaining sum divisible by `p`. Update `minLength = min(minLength, j - i + 1)`.
9. After the loops complete, if `minLength` is still `n`, it means no suitable subarray was found (or the only one was the entire array, which is not allowed). In this case, return -1. Otherwise, return `minLength`.

## Prefix Sum with Hash Map
This optimal approach leverages prefix sums and a hash map to solve the problem in linear time. The core idea is that the sum of a subarray `nums[i..j]` can be expressed as the difference between two prefix sums. By using modular arithmetic, we can transform the problem into finding two prefix sums with a specific relationship between their remainders.
**Time:** O(N), where N is the length of `nums`. We iterate through the array a constant number of times, and hash map operations take O(1) on average. · **Space:** O(min(N, P)). The hash map can store at most `P` distinct remainders. If `N < P`, it will store at most `N+1` key-value pairs.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; Solves the problem in a single pass after an initial pass to calculate the total sum.
**Cons:** Requires extra space for the hash map, which can be up to O(min(N, P)).; The logic is more complex than the brute-force approach.
### Explanation
The problem asks for the shortest subarray `nums[i..j]` such that `sum(nums[i..j]) % p == target_rem`, where `target_rem = sum(nums) % p`.

Let `prefixSum[k]` be the sum of elements from `nums[0]` to `nums[k]`. Then `sum(nums[i..j]) = prefixSum[j] - prefixSum[i-1]`. The condition becomes `(prefixSum[j] - prefixSum[i-1]) % p == target_rem`.

Let's work with remainders. Let `rem_j = prefixSum[j] % p` and `rem_i_minus_1 = prefixSum[i-1] % p`. The equation is `(rem_j - rem_i_minus_1 + p) % p == target_rem`. We can rearrange this to find the remainder we're looking for: `rem_i_minus_1 = (rem_j - target_rem + p) % p`.

This means that as we iterate through the array and calculate the prefix sum remainder `rem_j` at each index `j`, we can look for a previously seen prefix sum remainder `rem_i_minus_1` that satisfies the condition. A hash map is perfect for this: we can store the remainders of prefix sums we've seen so far and the latest index at which they occurred.

We iterate through the array, maintaining the current prefix sum. At each index `j`, we calculate the `current_rem`. Then we calculate the `needed_rem` as shown above. We query the hash map for this `needed_rem`. If found at index `i-1`, we have a candidate subarray from `i` to `j`, and we update our minimum length. We then store the `current_rem` and its index `j` in the map for future lookups.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int minSubarray(int[] nums, int p) {
        int n = nums.length;
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        int targetRem = (int)(totalSum % p);
        if (targetRem == 0) {
            return 0;
        }

        Map<Integer, Integer> remainderMap = new HashMap<>();
        remainderMap.put(0, -1); // Base case for subarrays starting at index 0
        int minLength = n;
        long currentSum = 0;

        for (int j = 0; j < n; j++) {
            currentSum += nums[j];
            int currentRem = (int)(currentSum % p);
            
            int neededRem = (currentRem - targetRem + p) % p;
            
            if (remainderMap.containsKey(neededRem)) {
                int prevIndex = remainderMap.get(neededRem);
                minLength = Math.min(minLength, j - prevIndex);
            }
            
            remainderMap.put(currentRem, j);
        }

        return minLength == n ? -1 : minLength;
    }
}
```
### Algorithm
1. Calculate `totalSum` of `nums` and find the remainder `target_rem = totalSum % p`.
2. If `target_rem == 0`, return 0.
3. Initialize a `HashMap<Integer, Integer>` called `remainderMap` to store `(remainder, last_index)` pairs. Add a base case `remainderMap.put(0, -1)` to handle subarrays that start from index 0.
4. Initialize `minLength = n` and `currentSum = 0`.
5. Iterate through the array with index `j` from `0` to `n-1`:
   a. Add `nums[j]` to `currentSum`.
   b. Calculate the current prefix sum remainder: `current_rem = currentSum % p`.
   c. We need to find a previous prefix sum whose remainder `prev_rem` satisfies `(current_rem - prev_rem) % p == target_rem`. This means we are looking for `needed_rem = (current_rem - target_rem + p) % p`.
   d. Check if `remainderMap` contains `needed_rem`. If it does, it means a subarray ending at `j` with the desired sum exists. The start of this subarray is `remainderMap.get(needed_rem) + 1`. Calculate its length `j - remainderMap.get(needed_rem)` and update `minLength`.
   e. Store the current prefix sum's remainder and its index: `remainderMap.put(current_rem, j)`.
6. After the loop, if `minLength` remains `n` or is not updated, it's impossible. Return -1. Otherwise, return `minLength`.

# Solutions
### Java

```java
class Solution {
public
  int minSubarray(int[] nums, int p) {
    int k = 0;
    for (int x : nums) {
      k = (k + x) % p;
    }
    if (k == 0) {
      return 0;
    }
    Map<Integer, Integer> last = new HashMap<>();
    last.put(0, -1);
    int n = nums.length;
    int ans = n;
    int cur = 0;
    for (int i = 0; i < n; ++i) {
      cur = (cur + nums[i]) % p;
      int target = (cur - k + p) % p;
      if (last.containsKey(target)) {
        ans = Math.min(ans, i - last.get(target));
      }
      last.put(cur, i);
    }
    return ans == n ? -1 : ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} p * @return {number} */ var minSubarray =
  function (nums, p) {
    let k = 0;
    for (const x of nums) {
      k = (k + x) % p;
    }
    if (k === 0) {
      return 0;
    }
    const last = new Map();
    last.set(0, -1);
    const n = nums.length;
    let ans = n;
    let cur = 0;
    for (let i = 0; i < n; ++i) {
      cur = (cur + nums[i]) % p;
      const target = (cur - k + p) % p;
      if (last.has(target)) {
        const j = last.get(target);
        ans = Math.min(ans, i - j);
      }
      last.set(cur, i);
    }
    return ans === n ? -1 : ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int minSubarray(vector<int> &nums, int p) {
    int k = 0;
    for (int &x : nums) {
      k = (k + x) % p;
    }
    if (k == 0) {
      return 0;
    }
    unordered_map<int, int> last;
    last[0] = -1;
    int n = nums.size();
    int ans = n;
    int cur = 0;
    for (int i = 0; i < n; ++i) {
      cur = (cur + nums[i]) % p;
      int target = (cur - k + p) % p;
      if (last.count(target)) {
        ans = min(ans, i - last[target]);
      }
      last[cur] = i;
    }
    return ans == n ? -1 : ans;
  }
};

```

### Python

```python
class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int: k = sum(nums) % p if k == 0: return 0 last = {0: - 1} cur = 0 ans = len(nums) for i, x in enumerate(nums): cur = (cur + x) % p target = (cur - k + p) % p if target in last: ans = min(ans, i - last[target]) last[cur] = i return - 1 if ans == len(nums) else ans

```