C++, Prefix Sum. Simple Logic. Must Know for SDE interviews. Easy to Understand
Idea: \n\nAs we need to delete a subbarray. We need to compute sum of subbarrays fast and efficient. The most popular technique is Prefix Sums. \n1. After delet
**Idea: **\n\nAs we need to delete a subbarray. We need to compute sum of subbarrays fast and efficient. The most popular technique is Prefix Sums. \n1. After deletion, the (sum of elements left in array) % p == 0.\n2. So (total array sum - deleted subbarray sum) % p = 0\n3. As we know, (a - b) % p = 0 ==> a % p = b % p\n4. So total sum % p , say Target = deleted subarray % p\n\nNow looking into the code, we first calculate the LHS of the above equation.\nThen we know that we need to find a subbarray whose sum % p == LHS. We calculate Prefix % p array, say P.\n1.  (P[i] - P[j] + p) % p == target\n2.  So for each i, we need a value  = (P[i] - target + p) % p from the Hashmap.\n3.  Note we use mod in above equation to handle negative cases, i.e target > P[i].\n4.  The Hasmap stores the latest occurence of P[j] % p for every j < i.\nLook into the code, for implementation details\n\n```\nclass Solution {\npublic:\n    int minSubarray(vector<int>& nums, int p) {\n        int n = nums.size();\n        int target = 0;\n        for(auto el: nums) target = (target + el) % p; // sum % k essentially\n        unordered_map<int, int> mp; // Our Hasmap\n        mp[0] = -1; // if we are looking for 0, we can take the complete subarray[0...i]\n        int cur = 0;\n        int ans = 1e9;\n        if(!target) return 0;\n        for(int i = 0; i<n; i++){\n            \n            cur = (cur + nums[i]) % p;\n            // we need to reach the target, lmao\n            int need = (cur - target + p) % p; // This is the element we are looking for\n            if(mp.find(need) != mp.end()){\n                ans = min(ans, i - mp[need]);\n            }\n            mp[cur] = i;  // hashing the current occurence as the latest occurence of cur % p\n        \n        }\n        \n        if(ans >= n) return -1; // we cannot delethe complete array, hence\n        return ans;\n    }\n};\n```\n
['C', 'Prefix Sum']