{"id":2428,"date":"2021-10-08T19:01:00","date_gmt":"2021-10-08T13:31:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2428"},"modified":"2021-10-08T16:04:13","modified_gmt":"2021-10-08T10:34:13","slug":"subarray-with-given-sum","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/subarray-with-given-sum\/","title":{"rendered":"Subarray With Given Sum"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#naive-approach\">Naive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#efficient-approach-sliding-window\">Efficient Approach: Sliding window<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-efficient-approach\">C++ Implementation of Efficient Approach<\/a><\/li><li><a href=\"#-java-implementation-of-efficient-approach\"><meta charset=\"utf-8\">Java Implementation of Efficient Approach<\/a><\/li><li><a href=\"#-python-implementation-of-efficient-approach\"><meta charset=\"utf-8\">Python Implementation of Efficient Approach<\/a><\/li><\/ul><li><a href=\"#practice-questions\">Practice Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given an array of integers, the task is to find a non-empty subarray that adds to the given sum. If there exists more than one print, anyone.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"273\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Array Integers\"  class=\"wp-image-2467 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Array-Integers-1024x273.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Array-Integers-1024x273.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Array-Integers-300x80.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Array-Integers-768x205.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Array-Integers-380x101.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Array-Integers-550x147.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Array-Integers-800x214.jpg 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Array-Integers.jpg 1150w\" ><\/figure><\/div>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<p><strong>Input:<\/strong> 11, 9, 8, 7,13, 5, 17<br><strong>Sum<\/strong> = 25<\/p>\n\n\n\n<p><strong>Output:<\/strong> YES<br><strong>Explanation:<\/strong> Subarray [7,13,5] sum up to 25 .<\/p>\n\n\n\n<p><strong>Input:<\/strong> 1,3,4,8,7,9<br><strong>Sum<\/strong> = 13<\/p>\n\n\n\n<p><strong>Output:<\/strong> No<br><strong>Explanation:<\/strong> No such subarray is present having sum 13.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"naive-approach\">Naive Approach<\/h2>\n\n\n\n<p>The naive approach is to check for every subarray for the given sum.<\/p>\n\n\n\n<ul><li>Run a loop for i from [0\u2026n-1] for the subarray starting from the i-th element.<\/li><li>And run a nested loop to check for every length of subarray starting from position i.<\/li><li>Every time check for the sum of the elements from i to j whether it\u2019s equal to the required sum.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"422\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Naive Approach - Subarray Sum\"  class=\"wp-image-2468 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Naive-Approach-Subarray-Sum-1024x422.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Naive-Approach-Subarray-Sum-1024x422.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Naive-Approach-Subarray-Sum-300x124.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Naive-Approach-Subarray-Sum-768x317.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Naive-Approach-Subarray-Sum-380x157.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Naive-Approach-Subarray-Sum-550x227.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Naive-Approach-Subarray-Sum-800x330.jpg 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Naive-Approach-Subarray-Sum-1160x478.jpg 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Naive-Approach-Subarray-Sum.jpg 1356w\" ><figcaption>Naive Approach &#8211; Subarray Sum<\/figcaption><\/figure>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool find_Subarray(int arr[], int N, int required) {\n  int sum = 0;\n  for (int i = 0; i &lt; N; i++) {\n    sum = arr[i];\n    for (int j = i + 1; j &lt; N + 1; j++) {\n      if (sum == required) {\n        \/\/ found subarray with given sum\n        return true;\n      } else if (sum > required) {\n        break;\n      }\n      sum = sum + arr[j];\n    }\n  }\n  return false;\n}<\/pre>\n\n\n\n<h3 id=\"java-implementation\">Java Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool find_subarray(int arr[], int N, int required) {\n  int sum;\n  for (int i = 0; i &lt; N; i++) {\n    sum = arr[i];\n    for (int j = i + 1; j &lt;= N; j++) {\n      if (sum == required) {\n        \/\/ subarray found from i to j-1;\n        return true;\n      }\n      if (sum > required || j == N)\n        break;\n      sum = sum + arr[j];\n    }\n  }\n  return false;\n}<\/pre>\n\n\n\n<h3 id=\"python-implementation\">Python Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def find_subarray(arr, n, required):\n\n    for i in range(n):\n        sum = arr[i]\n        j = i + 1\n        while j &lt;= n:\n            if sum == required:\n                return true\n            if sum > required or j == n:\n                break\n            sum = sum + arr[j]\n            j += 1\n    return false<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> O(N^2), Where N is the size of the array.<br><strong>Space complexity:<\/strong> O(1)<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-sliding-window\">Efficient Approach: Sliding window<\/h2>\n\n\n\n<p>In a sliding window we take an empty window and move the upper bound of the window till our given constraint is satisfied and after that, if the constraints are violated we try to maintain the constraints by increasing or decreasing the size of the window.<\/p>\n\n\n\n<p>The efficient approach is similar as we have constrained the sum and we take the window empty initially and if the sum of the window is greater than the required sum then it\u2019s clear that adding any element more will increase the sum, so we remove the elements from the starting of the window till the sum of the window is less than the required sum and move forward in a similar manner.<\/p>\n\n\n\n<ul><li>We have to take two variables one for the current sum and the other for the starting index of the window<\/li><li>Check if the current sum is less than or equal to the required sum.<\/li><li>If less then add the new element to the current sum.<\/li><li>If equal, return true.<\/li><li>If the current sum exceeds the required sum, subtract the arr[start] from the current sum and change start=start+1.<\/li><li>If we return from the nested loop then we could not find any desired subarray so return false.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"822\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Sliding Window Approach\"  class=\"wp-image-2469 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach-1024x822.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach-1024x822.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach-300x241.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach-768x617.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach-1536x1234.jpg 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach-380x305.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach-550x442.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach-800x643.jpg 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach-1160x932.jpg 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Sliding-Window-Approach.jpg 1565w\" ><\/figure>\n\n\n\n<h3 id=\"c-implementation-of-efficient-approach\">C++ Implementation of Efficient Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">bool FindSubarray(int array[], int n, int required_sum) {\n  int current_sum = array[0];\n  int start = 0;\n  for (int i = 1; i &lt;= n; i++) {\n    while (current_sum > required_sum &amp;&amp; start &lt; i - 1) {\n      current_sum = current_sum - array[start];\n      start++;\n    }\n    if (current_sum == required_sum) {\n      return true;\n    }\n    if (i &lt; n) {\n      current_sum = current_sum + array[i];\n    }\n  }\n  return false\n}<\/pre>\n\n\n\n<h3 id=\"-java-implementation-of-efficient-approach\"><span id=\"java-implementation-of-efficient-approach\"><meta charset=\"utf-8\">Java Implementation of Efficient Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public static bool Find_Subarray(int array[], int n, int required) {\n  int sum = array[0];\n  int start = 0;\n  for (int i = 1; i &lt;= n; i++) {\n    while (sum > required &amp;&amp; start &lt; i - 1) {\n      sum = sum - array[start];\n      start++;\n    }\n    if (sum == required) {\n      return true;\n    }\n    if (i &lt; n) {\n      sum = sum + array[i];\n    }\n  }\n  return false;\n}<\/pre>\n\n\n\n<h3 id=\"-python-implementation-of-efficient-approach\"><span id=\"python-implementation-of-efficient-approach\"><meta charset=\"utf-8\">Python Implementation of Efficient Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def Find_Subarray(array, n, required):\n\n    sum = array[0]\n    start = 0\n    i = 1\n    while i &lt;= n:\n\n        while sum > required and start &lt; i - 1:\n\n            sum = sum - array[start]\n            start += 1\n        if sum == required:\n            return true\n\n        if i &lt; n:\n            sum = sum + array[i]\n        i += 1\n\n    return false<\/pre>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-questions\">Practice Questions<\/h2>\n\n\n\n<p><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/counting-subarrays\/\" target=\"_blank\">Counting Subarrays<\/a><br><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/max-product-subarray\/\" target=\"_blank\">Maximum Product Subarray<\/a><br><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/subarrays-with-distinct-integers\/\" target=\"_blank\">Subarrays With Distinct Integers<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given an array of integers, the task is to find a non-empty subarray that adds to&hellip;\n","protected":false},"author":5,"featured_media":2532,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[405],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2428"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2428"}],"version-history":[{"count":2,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2428\/revisions"}],"predecessor-version":[{"id":2470,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2428\/revisions\/2470"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2532"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2428"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2428"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}