> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/hashmap-and-hashset-and-sliding-window/make-sum-divisible-by-p.md).

# Make Sum Divisible by P

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:**

<pre><code><strong>Input: nums = [3,1,4,2], p = 6
</strong><strong>Output: 1
</strong><strong>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.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [6,3,5,2], p = 9
</strong><strong>Output: 2
</strong><strong>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.
</strong></code></pre>

**Example 3:**

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

&#x20;

**Constraints:**

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

### Answer

```java
class Solution {
    public int minSubarray(int[] nums, int p) {
        long sum = 0;
        for (int x : nums) {
            sum += (long) x;
        }
        // It is not allowed to remove the whole array
        if (sum < p)
            return -1;
        sum = sum % p;
        if (sum == 0)
            return 0;
        // Now we want to find the smallest sub-array whose sum
        // is equal to 'sum' or 'sum' + p' or 'sum' + 2*p...
        Map<Integer, Integer> map = new HashMap<>();
        int ans = nums.length;
        long currSum = 0;
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            currSum += nums[i];
            int mod = (int) (currSum % p);
            map.put(mod, i);
            // +p because of property of mod
            int otherPart = (mod - (int) sum + p) % p;
            if (map.containsKey(otherPart))
                ans = Math.min(ans == -1 ? Integer.MAX_VALUE : ans, i - map.get(otherPart));
        }
        return ans < nums.length ? ans : -1;
    }
}
```