# LeetCode 1590. Make Sum Divisible by P

https://leetcode.com/problems/make-sum-divisible-by-p/description/

## 題目大意

給定正整數陣列 `nums` 移除非原陣列長的最小長度子陣列 (可以為空) 使得剩餘元素和可以被整數 `p` 整除

回傳該最小長度，若不存在則回傳 `-1`

## 思考

使用 `unordered_map` 建立 prefix remainder 與 index 的映射

class Solution
{
public:
    int minSubarray(vector<int> &nums, int p)
    {
        const int n = nums.size();
        const int r = accumulate(nums.begin(), nums.end(), 0LL) % p;

        if (!r)
            return 0;

        unordered_map<int, int> prefixIdx{{0, -1}};
        int rPrefix = 0, ans = n;

        for (int i = 0; i < n; ++i)
        {
            rPrefix = (rPrefix + nums[i]) % p;
            auto it = prefixIdx.find((rPrefix + p - r) % p);

            if (it != prefixIdx.end())
                ans = min(ans, i - it->second);

            prefixIdx[rPrefix] = i;
        }

        return ans != n ? ans : -1;
    }
};