# LeetCode #523: Continuos Subarray Sum

**Published by:** [Coder OP](https://paragraph.com/@coder-op/)
**Published on:** 2022-11-06
**URL:** https://paragraph.com/@coder-op/leetcode-523-continuos-subarray-sum

## Content

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 jsum_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 jLets do a dry run on first example:Given, nums : 23 2 4 6 7 , k = 6Prefix_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 satisfiedCode: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; }

## Publication Information

- [Coder OP](https://paragraph.com/@coder-op/): Publication homepage
- [All Posts](https://paragraph.com/@coder-op/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@coder-op): Subscribe to updates