# Continuous Subarray Sum

Leetcode 523. Continuous Subarray Sum

##### Problem

Given an integer array `nums` and an integer `k`, return `true` if `nums` has a continuous subarray of size at least two whose elements sum up to a multiple of `k`, or `false` otherwise.

An integer `x` is a multiple of `k` if there exists an integer `n` such that `x = n * k``0` is always a multiple of `k`.

Example 1:

```Input: nums = [23,2,4,6,7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.
```

Example 2:

```Input: nums = [23,2,6,4,7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
```

Example 3:

```Input: nums = [23,2,6,4,7], k = 13
Output: false
```

Constraints:

• `1 <= nums.length <= 105`
• `0 <= nums[i] <= 109`
• `0 <= sum(nums[i]) <= 231 - 1`
• `1 <= k <= 231 - 1`
##### Solution
###### A naive approach

The simplest way to think of this problem is taking cumulative sum from an index up to the end of the array and check if any of those sums % k = 0 or not. We will have to do this for each index and this will definitely give a solution.

`But this approach will cost us O(N2) [O N square] runtime which is not efficient and we don't want that! So, let's not waste time on it. If you want, you can think of it and even try it to some coding practice. No harm in doing that if you have enough time, right?`
###### A better approach

The naive approach is not so bad as we might think, at least it will be thought provoking for the better approach which we will show in a moment.

Unlike the naive approach, we will still take cumulative sum but only from the beginning of the array. But how it will help?

To answer this question, let’s think about what it means for a contiguous subarray sum divisible by k?

This means the sum of that portion of the array modulus k is 0! Let’s say we started to take cumulative sum from the beginning and at some point A, we found p = A % k [p is some arbitrary number].

We continue moving and doing the cumulative sum and after some time at some point B, we again found p = B % k [p is some arbitrary number].

So, for point A and B, A % k = B % k

which means, B % kA % k = 0

in other words, (BA) % k = 0

What does this mean? This means, the cumulative some difference from B to A is divisible by k, in other words, the subarray sum from A to B is divisible by k!

Let’s have a look at the below image if you find hard time to understand the concept.

###### Implementation

Now we have the basic, we can think about how to implement it.

All we need is to run a for loop from the beginning of the array and take cumulative sum in a variable. Also we take cumulative sum mod k (to know the p, an arbitrary number) and save p somewhere. If any point, we find that the same p was found before, we can tell that the point where it is found now and the point where it was found before -are the two points of our contiguous subarray whose sum is divisible by k.

To save p values and their location, we can simply use a hash map with key as p values and value as index (location). Also, we need to check the length of contiguous subarray should be at least 2.

Below images describe the implementation more clearly (hopefully!).

###### Implementation Details

Let’s say we have an array as below. We also have k = 10 and a map m initialized with m[0] = -1 (why? please think about it! You can try submitting your code without this initialization, when you will get wrong answer or something, play with the test cases and try to understand why this initialization is crucial! If you find out why, please do a favour to explain in comment 🙂 )

Now, we started our for loop and added up the cumulative sum and cumulative sum mod k (p value). Plus we started to save the p value and location (index) in the map as below.

We continue doing the same for index 1….

And for index 2 … but wait! For index 2 the p value is 5 which was seen at index 0…. and is 2 – 0 >= 2 ? very hard question!

So, this is how we find the answer.

##### Complexity

Since we are running the loop once, it’s an O(N) time complexity thing. For using map, we need extra space of O(N) as well.

##### Code
###### C++
```class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {

if(nums.size() < 2)
return false;

map<int, int> m;
m[0] = -1; //This is CRITICAL!!!!!!!!!!! Think why it is critical and answer in comment :)
int cumulative_sum = 0;
for(int i = 0; i < nums.size(); i++){
cumulative_sum += nums[i];
int res = 0;
if(k > 0)
res = cumulative_sum % k;

if(m.find(res) != m.end()){
if(i - m[res] > 1) return true;
}

if(m.find(res) == m.end())
m[res] = i;
}

return false;
}
};```
##### Conclusion

Hope you enjoyed this post. If you do, please write your feedback in the comment. If you did not enjoy, please write about your anger, frustration as well! We are always open to any kind of feedback.

Happy coding! 🙂

## 81 thoughts on “Continuous Subarray Sum”

1. Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.

2. Hello foolishhungry.com webmaster, Thanks for the well-presented post!

3. Hi foolishhungry.com admin, Your posts are always well-supported by facts and figures.

6. Dear foolishhungry.com owner, Thanks for the valuable information!

7. I genuinely enjoy reading on this web site, it has got excellent posts.

8. Dear foolishhungry.com owner, Your posts are always well-balanced and objective.

9. Bonito Designs, Building No 1182 Floor, 2, 5th Main Rd, 7th Sector, HSR Layout, Bengaluru, Karnataka 560102 Phone: 080660 85646 bonito.in/interior-designers-in-bangalore/

11. [url=https://lisinopril.best/]zestril 2.5[/url]

12. [url=https://ivermectin.cfd/]stromectol tablets 3 mg[/url]

13. [url=http://neurontin.cyou/]gabapentin 3000 mg[/url]

14. [url=https://lyrica.cfd/]lyrica cap 75mg[/url]

15. [url=http://baclofen.cfd/]where can i get baclofen[/url]

16. Hello foolishhungry.com admin, Your posts are always well structured and easy to follow.

17. [url=https://albuterol.guru/]how to get albuterol cheap[/url]

18. Thanks for sharing superb informations. Your website is so cool. I’m impressed by the details that you have on this site. It reveals how nicely you perceive this subject. Bookmarked this website page, will come back for more articles. You, my friend, ROCK! I found just the info I already searched all over the place and just could not come across. What a perfect website.

19. Heya i’m for the first time here. I came across this board and I find It truly useful & it helped me out much. I’m hoping to provide one thing again and aid others like you helped me.

20. [url=http://colchicine.cyou/]colchicine coupon[/url]

21. [url=https://robaxin.cyou/]robaxin otc[/url]

22. [url=http://azithromycin.digital/]cost of azithromycin 500 mg in india[/url]

23. [url=https://suhagra.cyou/]suhagra 25[/url]

24. This is really interesting, You’re a very skilled blogger. I’ve joined your feed and look forward to seeking more of your magnificent post. Also, I’ve shared your site in my social networks!

26. The standard chunk of Lorem Ipsum used since the 1500s is reproduced below for those interested.

27. [url=https://lisinopril.cfd/]zestril[/url]

28. [url=https://doxycycline.cyou/]doxycycline generic cost[/url]

30. To the foolishhungry.com admin, You always provide practical solutions and recommendations.

31. [url=https://azithromycin.digital/]azithromycin 1000 mg for sale[/url]

32. [url=https://avana.cfd/]dapoxetine nz[/url]

33. [url=http://amoxicillin.boutique/]brand name augmentin[/url]

35. [url=https://synthroid.directory/]where can i purchase synthroid[/url]

36. To the foolishhungry.com administrator, Thanks for the well-researched and well-written post!

37. [url=https://pharmacyonline.cfd/]online pharmacy for sale[/url]

38. [url=https://onlinepharmacy.cyou/]pharmacy in canada for viagra[/url]

39. [url=http://finasteride.digital/]finasteride cheap[/url]

40. [url=https://neurontin.cyou/]gabapentin brand[/url]

41. [url=http://synthroid.directory/]synthroid 150 mg[/url]

42. [url=https://azithromycin.digital/]zithromax.com[/url]

43. [url=http://atarax.cyou/]atarax for ic[/url]

44. [url=http://neurontin.cyou/]gabapentin online india[/url]

45. [url=http://finasteride.best/]purchase propecia online[/url]

46. [url=http://zithromax.cyou/]where can you buy azithromycin in australia[/url]

47. [url=https://levitra.cfd/]how to buy levitra in usa[/url]

48. [url=http://rybelsus.best/]wegovy without prescription[/url]

49. Наша группа профессиональных специалистов приготовлена предложить вам актуальные подходы, которые не только предоставят надежную протекцию от холодильности, но и подарят вашему зданию элегантный вид.
Мы практикуем с новейшими материалами, утверждая постоянный время использования и превосходные эффекты. Изоляция фронтонов – это не только сокращение расходов на отапливании, но и заботливость о экосистеме. Спасательные подходы, какие мы претворяем в жизнь, способствуют не только дому, но и сохранению природных ресурсов.
Самое ключевое: [url=https://ppu-prof.ru/]Наружное утепление фасада цена[/url] у нас составляет всего от 1250 рублей за метр квадратный! Это доступное решение, которое сделает ваш хаус в истинный тепличный корнер с минимальными затратами.
Наши пособия – это не исключительно теплоизоляция, это создание области, в где каждый член отражает ваш уникальный образ. Мы примем в расчет все ваши требования, чтобы преобразить ваш дом еще больше приятным и привлекательным.
Подробнее на [url=https://ppu-prof.ru/]http://ppu-prof.ru[/url]
Не откладывайте труды о своем корпусе на потом! Обращайтесь к специалистам, и мы сделаем ваш дом не только теплее, но и моднее. Заинтересовались? Подробнее о наших сервисах вы можете узнать на веб-ресурсе. Добро пожаловать в мир спокойствия и уровня.

50. [url=https://rybelsussemaglutide.com/]generic rybelsus[/url]

51. [url=https://semaglutide.cfd/]ozempic tablets for weight loss[/url]

52. [url=http://ozempic.monster/]rybelsus rx[/url]

54. [url=https://rybelsussemaglutide.online/]purchase rybelsus[/url]

55. It was impossible for me to leave your website without expressing my gratitude for the excellent knowledge you give your visitors. Without a doubt, I’ll be checking back frequently to see what updates you’ve made.

56. [url=http://semaglutide.quest/]rybelsus xl[/url]

57. [url=http://ozempic.cfd/]semaglutide generic cost[/url]

59. [url=http://ozempic.quest/]semaglutide weight loss[/url]

61. [url=https://semaglutide.pics/]generic ozempic cost[/url]

62. [url=https://semaglutidetabs.shop/]rybelsus tablets for weight loss[/url]

63. [url=https://ozempic.pics/]rybelsus 7 mg[/url]

65. [url=https://semaglutiderybelsus.shop/]rybelsus 7 mg[/url]

66. [url=http://semaglutide.guru/]semaglutide medication[/url]

67. [url=http://semaglutide.us.com/]purchase wegovy[/url]

68. [url=http://semaglutidewegovy.shop/]rybelsus tab 7mg[/url]

69. [url=https://ozempic.monster/]semaglutide generic[/url]