Table of Contents
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
Source: Leetcode 523. Continuous Subarray Sum
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 % k – A % k = 0
in other words, (B – A) % 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! 🙂
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.
Hello foolishhungry.com webmaster, Thanks for the well-presented post!
Hi foolishhungry.com admin, Your posts are always well-supported by facts and figures.
To the foolishhungry.com admin, Your posts are always a great read.
Dear foolishhungry.com administrator, Your posts are always a great read.
Dear foolishhungry.com owner, Thanks for the valuable information!
I genuinely enjoy reading on this web site, it has got excellent posts.
Dear foolishhungry.com owner, Your posts are always well-balanced and objective.
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/
Hello foolishhungry.com admin, Your posts are always informative.
diflucan 200mg
clonidine buy uk
buy amoxicillin from uk
zoloft pills 50mg
[url=https://lisinopril.best/]zestril 2.5[/url]
[url=https://ivermectin.cfd/]stromectol tablets 3 mg[/url]
[url=http://neurontin.cyou/]gabapentin 3000 mg[/url]
[url=https://lyrica.cfd/]lyrica cap 75mg[/url]
[url=http://baclofen.cfd/]where can i get baclofen[/url]
Hello foolishhungry.com admin, Your posts are always well structured and easy to follow.
[url=https://albuterol.guru/]how to get albuterol cheap[/url]
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.
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.
[url=http://colchicine.cyou/]colchicine coupon[/url]
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me? https://accounts.binance.com/cs/register?ref=S5H7X3LP
[url=https://robaxin.cyou/]robaxin otc[/url]
[url=http://azithromycin.digital/]cost of azithromycin 500 mg in india[/url]
[url=https://suhagra.cyou/]suhagra 25[/url]
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!
[url=http://tadalafil.cfd/]how to get tadalafil[/url]
The standard chunk of Lorem Ipsum used since the 1500s is reproduced below for those interested.
[url=https://lisinopril.cfd/]zestril[/url]
[url=https://doxycycline.cyou/]doxycycline generic cost[/url]
[url=https://tadalafil.cfd/]cialis cost in mexico[/url]
To the foolishhungry.com admin, You always provide practical solutions and recommendations.
[url=https://azithromycin.digital/]azithromycin 1000 mg for sale[/url]
[url=https://avana.cfd/]dapoxetine nz[/url]
[url=http://amoxicillin.boutique/]brand name augmentin[/url]
[url=https://finpecia.cyou/]buy finasteride 1mg australia[/url]
[url=https://synthroid.directory/]where can i purchase synthroid[/url]
To the foolishhungry.com administrator, Thanks for the well-researched and well-written post!
[url=https://pharmacyonline.cfd/]online pharmacy for sale[/url]
[url=https://onlinepharmacy.cyou/]pharmacy in canada for viagra[/url]
[url=http://finasteride.digital/]finasteride cheap[/url]
[url=https://neurontin.cyou/]gabapentin brand[/url]
[url=http://synthroid.directory/]synthroid 150 mg[/url]
[url=https://azithromycin.digital/]zithromax.com[/url]
[url=http://atarax.cyou/]atarax for ic[/url]
[url=http://neurontin.cyou/]gabapentin online india[/url]
[url=http://finasteride.best/]purchase propecia online[/url]
[url=http://zithromax.cyou/]where can you buy azithromycin in australia[/url]
[url=https://levitra.cfd/]how to buy levitra in usa[/url]
[url=http://rybelsus.best/]wegovy without prescription[/url]
Наша группа профессиональных специалистов приготовлена предложить вам актуальные подходы, которые не только предоставят надежную протекцию от холодильности, но и подарят вашему зданию элегантный вид.
Мы практикуем с новейшими материалами, утверждая постоянный время использования и превосходные эффекты. Изоляция фронтонов – это не только сокращение расходов на отапливании, но и заботливость о экосистеме. Спасательные подходы, какие мы претворяем в жизнь, способствуют не только дому, но и сохранению природных ресурсов.
Самое ключевое: [url=https://ppu-prof.ru/]Наружное утепление фасада цена[/url] у нас составляет всего от 1250 рублей за метр квадратный! Это доступное решение, которое сделает ваш хаус в истинный тепличный корнер с минимальными затратами.
Наши пособия – это не исключительно теплоизоляция, это создание области, в где каждый член отражает ваш уникальный образ. Мы примем в расчет все ваши требования, чтобы преобразить ваш дом еще больше приятным и привлекательным.
Подробнее на [url=https://ppu-prof.ru/]http://ppu-prof.ru[/url]
Не откладывайте труды о своем корпусе на потом! Обращайтесь к специалистам, и мы сделаем ваш дом не только теплее, но и моднее. Заинтересовались? Подробнее о наших сервисах вы можете узнать на веб-ресурсе. Добро пожаловать в мир спокойствия и уровня.
[url=https://rybelsussemaglutide.com/]generic rybelsus[/url]
[url=https://semaglutide.cfd/]ozempic tablets for weight loss[/url]
[url=http://ozempic.monster/]rybelsus rx[/url]
[url=https://ozempic.monster/]buy ozempic[/url]
[url=https://rybelsussemaglutide.online/]purchase rybelsus[/url]
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.
[url=http://semaglutide.quest/]rybelsus xl[/url]
[url=http://ozempic.cfd/]semaglutide generic cost[/url]
[url=http://semaglutideozempic.com/]buy semaglutide in mexico[/url]
[url=http://ozempic.quest/]semaglutide weight loss[/url]
[url=https://semaglutideozempic.com/]semaglutide tablets buy[/url]
[url=https://semaglutide.pics/]generic ozempic cost[/url]
[url=https://semaglutidetabs.shop/]rybelsus tablets for weight loss[/url]
I don’t think the title of your article matches the content lol. Just kidding, mainly because I had some doubts after reading the article. https://accounts.binance.com/sv/register?ref=B4EPR6J0
Your point of view caught my eye and was very interesting. Thanks. I have a question for you. https://www.binance.com/lv/join?ref=GJY4VW8W
[url=https://ozempic.pics/]rybelsus 7 mg[/url]
[url=http://rybelsus.click/]buy ozempic uk[/url]
[url=https://semaglutiderybelsus.shop/]rybelsus 7 mg[/url]
[url=http://semaglutide.guru/]semaglutide medication[/url]
[url=http://semaglutide.us.com/]purchase wegovy[/url]
[url=http://semaglutidewegovy.shop/]rybelsus tab 7mg[/url]
[url=https://ozempic.monster/]semaglutide generic[/url]
[url=http://rybelsus.party/]semaglutide where to buy[/url]
Уважаемые Клиенты!
Предлагаем вам новейшее концепцию в мире дизайна внутреннего пространства – шторы плиссе. Если вы движетесь к совершенству в всей нюансе вашего жилища, то эти гардины окажутся великолепным паттерном для вас.
Что делает шторы плиссе таковыми особенными? Они сочетают в себе в себе шик, использование и применимость. Благодаря эксклюзивной постройке, технологичным материалам, шторы плиссе идеально гармонизируются с для какова угодно интерьера, будь то гостинка, спальня, плитка или рабочее место.
Закажите [url=https://tulpan-pmr.ru]шторы плиссе[/url] – создайте уют и великолепие в вашем доме!
Чем манят шторы плиссе для вас? Во-первых, их самобытный образ, который присоединяет к привлекательность и шик вашему внутреннему пространству. Вы можете выискать из различных текстур, оттенков и подходов, чтобы выделить отличительность вашего дома.
Кроме того, шторы плиссе предлагают массивный круг функциональных возможностей. Они могут управлять уровень света в помещении, остерегать от солнечного света, поддерживать интимность и формировать уютную среду в вашем доме.
Мы сайт: [url=https://tulpan-pmr.ru]www.tulpan-pmr.ru[/url]
Мы сами поддержим вам выбрать шторы плиссе, какие идеально подойдут для вашего внутреннего пространства!
[url=https://wegovy.click/]rybelsus oral medication[/url]
Your point of view caught my eye and was very interesting. Thanks. I have a question for you. https://www.binance.com/join?ref=DB40ITMB
[url=http://ozempic.company/]semaglutide canada[/url]
[url=http://wegovy.guru/]ozempic online[/url]
Your article helped me a lot, is there any more related content? Thanks! https://www.binance.info/ph/join?ref=V3MG69RO
Thanks for sharing. I read many of your blog posts, cool, your blog is very good. https://accounts.binance.com/ru/register?ref=RQUR4BEO
[url=http://ozempic.guru/]rybelsus buy australia[/url]
[url=http://semaglutideozempic.com/]semaglutide medicine[/url]
This webpage is fabulous. The superb information shows the maker’s earnestness. I’m dazed and envision additional such incredible presents on.
[url=https://semaglutideozempic.online/]generic semaglutide for weight loss[/url]
[url=http://ozempictabs.online/]rybelsus oral medication[/url]
Simply wish to say your article is as amazing The clearness in your post is just nice and i could assume youre an expert on this subject Well with your permission let me to grab your feed to keep updated with forthcoming post Thanks a million and please carry on the gratifying work
[url=http://rybelsussemaglutide.shop/]ozempic tablets cost[/url]
[url=https://semaglutide.quest/]buy wegovy[/url]
[url=https://semaglutidetabs.shop/]rybelsus online prescription[/url]
[url=https://semaglutiderybelsus.online/]semaglutide canada pharmacy prices[/url]
[url=http://wegovy.company/]where to buy ozempic online[/url]
[url=https://happyfamilystorerx.online/]worldwide pharmacy online[/url]
[url=https://tadalafi.online/]cialis for daily use best price[/url]
[url=http://happyfamilymedicalstore.online/]pharmacy website india[/url]
Thanks for sharing. I read many of your blog posts, cool, your blog is very good.
[url=http://tadalafilstd.online/]cheapest tadalafil online compare prices[/url]
I don’t think the title of your article matches the content lol. Just kidding, mainly because I had some doubts after reading the article.
[url=https://drugstorepp.online/]online pharmacy discount code 2018[/url]
[url=https://bmtadalafil.online/]10 mg tadalafil tablets[/url]
sed asperiores itaque nihil aut tenetur tempore qui aut provident blanditiis esse eos nobis odit et. qui dolor consequatur deleniti voluptas libero architecto animi molestiae vel esse nesciunt temporibus facilis temporibus a ut qui et voluptatem. necessitatibus ipsa assumenda earum nam iusto fugiat iusto accusamus. laboriosam aut vel dicta voluptate accusamus qui et consequuntur labore nobis et labore voluptatem.
Notice that the Kick-Off Social gathering is made up of been rescheduled for June 12th owing in direction of the coming up with collapse inside of Heart Metropolis.Documented at
[url=https://ametformin.com/]glucophage for sale[/url]
[url=http://happyfamilystorerx.online/]best australian online pharmacy[/url]
[url=https://vatrex.online/]prescription for valtrex[/url]
What’s up, I check your new stuff on a regular basis.
Your story-telling style is awesome, keep up the good work!
[url=https://azithromycinps.online/]zithromax for sale us[/url]
[url=http://bmtadalafil.online/]buy tadalafil usa online[/url]
[url=http://vatrex.online/]valtrex online prescription[/url]
[url=https://happyfamilymedicalstore.online/]happy family pharmacy[/url]
Мы группа специалистов по продвижению в интернете, занимающихся увеличением трафика и улучшением рейтинга вашего сайта в поисковых системах.
Мы получили признание за свою работу и готовы поделиться с вами нашими знаниями и опытом.
Что мы можем вам предложить:
• [url=https://seo-prodvizhenie-ulyanovsk1.ru/]сео продвижение сайта яндекс репутационные работы[/url]
• Полный аудит вашего сайта и создание индивидуальной стратегии продвижения.
• Оптимизация контента и технических характеристик вашего сайта для достижения наивысших результатов.
• Ежедневный анализ данных и мониторинг вашего онлайн-присутствия для постоянного улучшения его эффективности.
Подробнее [url=https://seo-prodvizhenie-ulyanovsk1.ru/]https://seo-prodvizhenie-ulyanovsk1.ru/[/url]
Уже сейчас наши клиенты получают результаты: увеличение трафика, улучшение позиций в поисковых системах и, конечно же, рост прибыли. Мы готовы предоставить вам бесплатную консультацию, для обсуждения ваших требований и разработки стратегии продвижения, соответствующей вашим целям и бюджету.
Не упустите возможность улучшить свои позиции в интернете. Свяжитесь с нами прямо сейчас.
[url=https://bmtadalafil.online/]tadalafil from mexico[/url]
[url=https://happyfamilystorerx.online/]legitimate canadian mail order pharmacy[/url]
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me.
[url=http://tadalafilstd.com/]buy tadalafil paypal[/url]
[url=https://metoformin.online/]buy metformin canada[/url]
[url=http://medicinesaf.online/]canadian pharmacy sildenafil[/url]
laudantium molestiae animi recusandae veniam eaque ut quia iste tempore non nihil est. corrupti nisi quia enim incidunt eos quia unde occaecati. voluptatem doloribus sunt accusamus qui magnam corporis sit quibusdam.