C++| Prefix sum | O(N)
We do not need to store the sum, we just need to store the reminder.\nHow can Remainder Helps?\n Firstly, calculate the remainder for the sum of whole array. le
We do not need to store the sum, we just need to store the reminder.\n**How can Remainder Helps?**\n* Firstly, calculate the remainder for the sum of whole array. lets say its `r`. Now we know for sure that remainder of sum of subarray removed will be `r`.\n* Now, iterate through array, find sum from index `0` to `i`. suppose the remainder for sum[0,i] is `x`. what can be the possible candidates for remainder sum such that if subtracted from sum[0,i] will give remainder `r`?\n* Equation will be `( x - y + p)%p == r` where `y` is the remainder for possible candidate for sum. For Every `x` there are 2 possibility for `y`. either `x-y` is +ve or its -ve. Find the value of `y` for both the senarios, if **0<=y<p** holds, then check if we have found `y` remiander for any sum of subarray **[0,i-1]** previously, if yes, store the result. \n* Store the latest index of every `x` as `map[x] = i`\n ```\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        map<int,int> mp;\n        long long sum = 0;\n        for(int i = 0; i<nums.size();++i) sum+=nums[i];\n        int r = sum%p,re=INT_MAX; sum = 0; mp[0] = -1;\n        if(r==0) return 0;\n        for(int i=0; i<nums.size();++i){\n            sum+=nums[i];\n            int x = sum%p, t = x-r; // case 1 when `x-y` is +ve \n            if(t>=0 && t<p && mp.find(t)!=mp.end()) re = min(re,i-mp[t]);\n            t = x+p-r;  // case 2 when `x-y` is -ve \n            if(t>=0 && t<p && mp.find(t)!=mp.end()) re = min(re,i-mp[t]);\n            mp[x] = i;  // store the latest index for remainder x as we want subarray to be smallest.\n        }\n        if(re==nums.size()) re=-1;\n        return re;\n    }\n};\n```
['C', 'Prefix Sum']