Description Link to heading

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 = 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 <= 10⁵
  • 1 <= nums[i] <= 10⁹
  • 1 <= p <= 10⁹

Solution Link to heading

We can use a prefix sum array to store the remainder of the sum of the first ith elements. We denote mod as the remainder of the sum of all the elements. Then we need to find a subarray whose sum mod p is mod too.

We can use a hash table to solve the problem. The key is the remainder of prefix[i], value is i. We traverse the prefix sum array, and update the hash table.

If prefix[i] % p == tmp_mod, then we need to find if key (tmp_mod - mod + p) % p is in the hash table. If it is, res = std::min(res, ump[tmp_mod] - ump[(tmp_mod - mod + p) % p]).

Code Link to heading 

class Solution {
  public:
    int minSubarray(vector<int> &nums, int p) {
        int n = nums.size();
        vector<int> prefix(n + 1);
        for (int i = 1; i <= n; ++i) {
            prefix[i] = (prefix[i - 1] + nums[i - 1]) % p; 
        }
        int mod = prefix[n] % p;
        if (mod == 0) {
            return 0;
        }
        unordered_map<int, int> ump;
        ump[0] = 0;
        int res = n;
        for (int i = 1; i <= n; ++i) {
            int tmp_mod = prefix[i] % p;
            ump[tmp_mod] = i;
            if (ump.find((tmp_mod - mod + p) % p) != ump.end()) {
                res = std::min(res, i - ump[(tmp_mod - mod + p) % p]);
            }
        }
        if (res == n) {
            return -1;
        }
        return res;
    }
};