Beats 100% || C++ || Prefix Sum || Maths
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks us to find the minimum-length subarray that, when removed, makes the s
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks us to find the minimum-length subarray that, when removed, makes the sum of the remaining array divisible by p. We can utilize modular arithmetic to approach this.\nIf the sum of the entire array total leaves a remainder rem when divided by p (i.e., total % p = rem), then we need to remove a subarray whose sum leaves the remainder rem when divided by p. Once we find such a subarray, removing it would ensure that the remaining sum becomes divisible by p.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tInitial Check: First, compute the total sum of the array. If total % p == 0, then the sum is already divisible by p, and no subarray needs to be removed, so the result is 0.\n2.\tPrefix Sum and Hashing:\n\t\u2022\tUse a prefix sum to keep track of the cumulative sum modulo p.\n\t\u2022\tStore each prefix sum\u2019s remainder in a hash map (unordered map), where the key is the remainder, and the value is the index at which it was encountered.\n\t\u2022\tThe idea is to find the shortest subarray that, when removed, reduces the total remainder by rem. This can be done by calculating, at every index i, what the remainder t = (presum - rem + p) % p would be. If this remainder has been seen before at some index j, then the subarray from j + 1 to i is a candidate for removal.\n3.\tTrack the Minimum Length: As you scan through the array, keep track of the minimum length of such subarrays by comparing the difference between the current index i and the index where the desired remainder t was last seen.\n4.\tFinal Check: If no such subarray is found (i.e., if the minimum length is still the size of the array n), return -1. Otherwise, return the minimum length found.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\n#define ll long long\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        int n = nums.size();\n        ll total = accumulate(nums.begin(), nums.end(), 0LL);\n        int rem = total % p;\n        if(rem == 0) return 0;\n\n        unordered_map<int,int> mp;\n        int presum = 0;\n        mp[0] = -1;\n        int minlen = n;\n\n        for(int i=0; i<n; i++){\n            presum = (presum + nums[i]) % p;\n            int t = (presum - rem + p) % p;\n            if(mp.find(t) != mp.end()) minlen = min(minlen, i-mp[t]);\n            mp[presum] = i; \n        }\n\n        return minlen == n ? -1 : minlen;\n    }\n};\n\nauto speedup = [](){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();\n```
['Array', 'Hash Table', 'Math', 'Prefix Sum', 'C++']