Formatted question description: https://leetcode.ca/all/1590.html

# 1590. Make Sum Divisible by P (Medium)

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 = 6Output:1Explanation: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 = 9Output:2Explanation: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 = 3Output:0Explanation:Here the sum is 6. which is already divisible by 3. Thus we do not need to remove anything.

**Example 4:**

Input:nums = [1,2,3], p = 7Output:-1Explanation:There is no way to remove a subarray in order to get a sum divisible by 7.

**Example 5:**

Input:nums = [1000000000,1000000000,1000000000], p = 3Output:0

**Constraints:**

`1 <= nums.length <= 10`

^{5}`1 <= nums[i] <= 10`

^{9}`1 <= p <= 10`

^{9}

**Related Topics**:
Array, Binary Search

**Similar Questions**:

## Solution 1. Prefix State Map

```
// OJ: https://leetcode.com/problems/make-sum-divisible-by-p
// Time: O(N)
// Space: O(N)
class Solution {
public:
int minSubarray(vector<int>& A, int p) {
long N = A.size(), sum = 0, total = 0, ans = N;
for (int n : A) total = (total + n) % p;
if (total == 0) return 0;
unordered_map<int, int> m{ {0,-1} };
for (int i = 0; i < N; ++i) {
sum = (sum + A[i]) % p;
int r = (sum - total + p) % p;
if (m.count(r)) ans = min(ans, (long)i - m[r]);
m[sum] = i;
}
return ans == N ? -1 : ans;
}
};
```

Java

```
class Solution {
public int minSubarray(int[] nums, int p) {
int sum = 0;
int length = nums.length;
for (int i = 0; i < length; i++)
sum = (sum + nums[i]) % p;
if (sum == 0)
return 0;
int remainder = sum;
sum = 0;
int minLength = length;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(0, -1);
for (int i = 0; i < length; i++) {
sum = (sum + nums[i]) % p;
int prev = (sum - remainder + p) % p;
if (map.containsKey(prev)) {
int curLength = i - map.get(prev);
minLength = Math.min(minLength, curLength);
}
map.put(sum, i);
}
return minLength == length ? -1 : minLength;
}
}
```