# LeetCode #523: Continuos Subarray Sum

By [Coder OP](https://paragraph.com/@coder-op) · 2022-11-06

---

**Intution :**

*   We need a subarray say from i to j such that sum of all elements is divisible by k.
    
    *   sum\_j means prefix sum from 0 to j
        
    *   sum\_i means prefix sum from 0 to i
        
             => (sum_j - sum_i) % k = 0
             => sum_j % k - sum % k = 0
             => sum_j % k = sum_i % k    <Relation derived !!!>
            
        
*   Thus for some prefix\_sum(0,j) , we need to check if there exist some prefix\_sum(0,i) such that both are equal.
    
    *   If yes then return true.
        
    *   Otherwise check for some other j
        
*   Lets do a dry run on first example:
    
    *   Given, nums : 23 2 4 6 7 , k = 6
        
    *   Prefix\_Sum at every iteration from 0->i :
        
              i = 0  , prefixSum = 23%6 = 5       | map[5] = 0 (new entry)
              i = 1 , prefixSum = (5+2)%6 = 1     | map[1] = 1 (new entry)
              i = 2 , prefixSum = (1+4)%6 = 5     | map[5] (already exist) !! -> Possible answer
            
        
    *   _Also, i - map\[5\] = 2 > 1 ... therefore at least 2 elements condition is also satisfied_
        

### Code:

    bool checkSubarraySum(vector<int>& nums, int k) {
         
        int prefSum = 0;
        unordered_map<int, int> mp;
        for(int i=0; i<nums.size(); i++)
        {
            prefSum += nums[i];
            prefSum %= k;
    
            if(prefSum == 0 && i) return true;
    
            // cout << prefSum << " ";
            if(mp.find(prefSum) != mp.end())  // Found the required prefix sum 
            {
                if(i - mp[prefSum] > 1) return true; // check if atleast 2 elements are there or not
            }
            else mp[prefSum] = i;
        }
    
        return false;
    }

---

*Originally published on [Coder OP](https://paragraph.com/@coder-op/leetcode-523-continuos-subarray-sum)*