Find Subarray with given sum | Set 1 (Non-negative Numbers)
Given an array arr[] of non-negative integers and an integer sum, find a subarray that adds to a given sum.
Note: There may be more than one subarray with sum as the given sum, print first such subarray.
Examples:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4
Explanation: Sum of elements between indices 2 and 4 is 20 + 3 + 10 = 33Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output: Sum found between indexes 1 and 4
Explanation: Sum of elements between indices 1 and 4 is 4 + 0 + 0 + 3 = 7Input: arr[] = {1, 4}, sum = 0
Output: No subarray found
Explanation: There is no subarray with 0 sum
Find subarray with given sum using Nested loop
The idea is to consider all subarrays one by one and check the sum of every subarray. Following program implements the given idea.
Run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from i.
Follow the steps given below to implement the approach:
- Traverse the array from start to end.
- From every index start another loop from i to the end of the array to get all subarrays starting from i, and keep a variable currentSum to calculate the sum of every subarray.
- For every index in inner loop update currentSum = currentSum + arr[j]
- If the currentSum is equal to the given sum then print the subarray.
Below is the implementation of the above approach.
/* A simple program to print subarray
with sum as given sum */
#include <bits/stdc++.h>
using namespace std;
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
void subArraySum(int arr[], int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
cout << "Sum found at indexes " << i << endl;
return;
}
else {
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
cout << "Sum found between indexes "
<< i << " and " << j << endl;
return;
}
}
}
}
cout << "No subarray found";
return;
}
// Driver Code
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
// This code is contributed
// by rathbhupendra
/* A simple program to print
subarray with sum as given sum */
#include <stdio.h>
/* Returns true if the there is a subarray
of arr[] with a sum equal to 'sum'
otherwise returns false. Also, prints
the result */
void subArraySum(int arr[], int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
printf("Sum found at indexe %d ", i);
return;
}
else {
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
printf("Sum found between indexes %d "
"and %d",
i, j);
return;
}
}
}
}
printf("No subarray found");
return;
}
// Driver program to test above function
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
public class SubarraySum {
/* Returns true if the there is a
subarray of arr[] with a sum equal to
'sum' otherwise returns false.
Also, prints the result */
void subArraySum(int arr[], int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
System.out.println("Sum found at indexe "
+ i);
return;
}
else {
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
System.out.println(
"Sum found between indexes " + i
+ " and " + j);
return;
}
}
}
}
System.out.println("No subarray found");
return;
}
public static void main(String[] args)
{
SubarraySum arraysum = new SubarraySum();
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = arr.length;
int sum = 23;
arraysum.subArraySum(arr, n, sum);
}
}
// This code has been contributed by Mayank
// Jaiswal(mayank_24)
# A simple program to print subarray with sum as given sum
# Returns true if the there is a subarray of arr[] with sum equal to 'sum' otherwise returns false. Also, prints the result
def subArraySum(arr, n, sum):
# Pick a starting point
for i in range(0,n):
currentSum = arr[i]
if(currentSum == sum):
print("Sum found at indexes",i)
return
else:
# Try all subarrays starting with 'i'
for j in range(i+1,n):
currentSum += arr[j]
if(currentSum == sum):
print("Sum found between indexes",i,"and",j)
return
print("No Subarray Found")
# Driver Code
if __name__ == "__main__":
arr = [15,2,4,8,9,5,10,23]
n = len(arr)
sum = 23
subArraySum(arr, n, sum)
# This code is contributed by ajaymakvana
using System;
public class HelloWorld
{
/* Returns true if the there is a subarray of arr[] with a sum equal to
'sum' otherwise returns false. Also, prints the result */
public static void subArraySum(int[] arr, int n, int sum)
{
// Pick a starting point
for (int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
Console.WriteLine("Sum found at indexe " + i);
return;
} else
{
// Try all subarrays starting with 'i'
for (int j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
Console.WriteLine("Sum found between indexes " + i + " and " + j);
return;
}
}
}
}
Console.WriteLine("No subarray found");
return;
}
public static void Main(string[] args) {
int[] arr = {15, 2, 4, 8, 9, 5, 10, 23};
int n = arr.Length;
int sum = 23;
subArraySum(arr, n, sum);
}
}
// This code is contributed by ajaymakavana.
/* A simple program to print subarray
with sum as given sum */
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
function subArraySum( arr, n, sum)
{
// Pick a starting point
for (let i = 0; i < n; i++) {
let currentSum = arr[i];
if (currentSum == sum) {
console.log("Sum found at indexes " +i);
return;
}
else {
// Try all subarrays starting with 'i'
for (let j = i + 1; j < n; j++) {
currentSum += arr[j];
if (currentSum == sum) {
console.log("Sum found between indexes "
+ i + " and " +j);
return;
}
}
}
}
console.log("No subarray found");
return;
}
let arr = [15, 2, 4, 8, 9, 5, 10, 23 ];
let n = arr.length;
let sum = 23;
subArraySum(arr, n, sum);
// This code is contributed by garg28harsh.
Output
Sum found between indexes 1 and 4
Time Complexity: O(N2), Trying all subarrays from every index, used nested loop for the same
Auxiliary Space: O(1).
Find subarray with given sum using Sliding Window
The idea is simple as we know that all the elements in subarray are positive so, If a subarray has sum greater than the given sum then there is no possibility that adding elements to the current subarray will be equal to the given sum. So the Idea is to use a similar approach to a sliding window.
- Start with an empty subarray
- add elements to the subarray until the sum is less than x( given sum ).
- If the sum is greater than x, remove elements from the start of the current subarray.
Follow the steps given below to implement the approach:
- Create two variables, start=0, currentSum = arr[0]
- Traverse the array from index 1 to end.
- Update the variable currentSum by adding current element, currentSum = currentSum + arr[i]
- If the currentSum is greater than the given sum, update the variable currentSum as currentSum = currentSum – arr[start],
and update start as, start++. - If the currentSum is equal to given sum, print the subarray and break the loop.
Below is the implementation of the above approach.
/* An efficient program to print
subarray with sum as given sum */
#include <iostream>
using namespace std;
/* Returns true if the there is a subarray of
arr[] with a sum equal to 'sum' otherwise
returns false. Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
/* Initialize currentSum as value of
first element and starting point as 0 */
int currentSum = arr[0], start = 0, i;
/* Add elements one by one to currentSum and
if the currentSum exceeds the sum,
then remove starting element */
for (i = 1; i <= n; i++) {
// If currentSum exceeds the sum,
// then remove the starting elements
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
// If currentSum becomes equal to sum,
// then return true
if (currentSum == sum) {
cout << "Sum found between indexes " << start
<< " and " << i - 1;
return 1;
}
// Add this element to currentSum
if (i < n)
currentSum = currentSum + arr[i];
}
// If we reach here, then no subarray
cout << "No subarray found";
return 0;
}
// Driver Code
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
// This code is contributed by SHUBHAMSINGH10
/* An efficient program to print
subarray with sum as given sum */
#include <stdio.h>
/* Returns true if the there is a
subarray of arr[] with a sum
equal to 'sum' otherwise returns
false. Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
/* Initialize currentSum as
value of first element and
starting point as 0 */
int currentSum = arr[0], start = 0, i;
/* Add elements one by one to
currentSum and if the currentSum
exceeds the sum, then remove
starting element */
for (i = 1; i <= n; i++) {
// If currentSum exceeds the sum,
// then remove the starting elements
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
// If currentSum becomes equal to sum,
// then return true
if (currentSum == sum) {
printf("Sum found between indexes %d and %d",
start, i - 1);
return 1;
}
// Add this element to currentSum
if (i < n)
currentSum = currentSum + arr[i];
}
// If we reach here, then no subarray
printf("No subarray found");
return 0;
}
// Driver program to test above function
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subArraySum(arr, n, sum);
return 0;
}
public class SubarraySum {
/* Returns true if the there is
a subarray of arr[] with sum equal to
'sum' otherwise returns false.
Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
int currentSum = arr[0], start = 0, i;
// Pick a starting point
for (i = 1; i <= n; i++) {
// If currentSum exceeds the sum,
// then remove the starting elements
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
// If currentSum becomes equal to sum,
// then return true
if (currentSum == sum) {
int p = i - 1;
System.out.println(
"Sum found between indexes " + start
+ " and " + p);
return 1;
}
// Add this element to curr_sum
if (i < n)
currentSum = currentSum + arr[i];
}
System.out.println("No subarray found");
return 0;
}
public static void main(String[] args)
{
SubarraySum arraysum = new SubarraySum();
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = arr.length;
int sum = 23;
arraysum.subArraySum(arr, n, sum);
}
}
// This code has been contributed by Mayank
// Jaiswal(mayank_24)
# An efficient program
# to print subarray
# with sum as given sum
# Returns true if the
# there is a subarray
# of arr[] with sum
# equal to 'sum'
# otherwise returns
# false. Also, prints
# the result.
def subArraySum(arr, n, sum_):
# Initialize currentSum as
# value of first element
# and starting point as 0
currentSum = arr[0]
start = 0
# Add elements one by
# one to currentSum and
# if the currentSum exceeds
# the sum, then remove
# starting element
i = 1
while i <= n:
# If currentSum exceeds
# the sum, then remove
# the starting elements
while currentSum > sum_ and start < i-1:
currentSum = currentSum - arr[start]
start += 1
# If currentSum becomes
# equal to sum, then
# return true
if currentSum == sum_:
print("Sum found between indexes % d and % d" % (start, i-1))
return 1
# Add this element
# to currentSum
if i < n:
currentSum = currentSum + arr[i]
i += 1
# If we reach here,
# then no subarray
print("No subarray found")
return 0
# Driver program
if __name__ == '__main__':
arr = [15, 2, 4, 8, 9, 5, 10, 23]
n = len(arr)
sum_ = 23
subArraySum(arr, n, sum_)
# This code is Contributed by shreyanshi_arun.
// An efficient C# program to print
// subarray with sum as given sum
using System;
class GFG {
// Returns true if the
// there is a subarray of
// arr[] with sum equal to
// 'sum' otherwise returns false.
// Also, prints the result
int subArraySum(int[] arr, int n, int sum)
{
int currentSum = arr[0], start = 0, i;
// Pick a starting point
for (i = 1; i <= n; i++) {
// If currentSum exceeds
// the sum, then remove
// the starting elements
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
// If currentSum becomes equal to
// sum, then return true
if (currentSum == sum) {
int p = i - 1;
Console.WriteLine("Sum found between "
+ "indexes " + start
+ " and " + p);
return 1;
}
// Add this element to currentSum
if (i < n)
currentSum = currentSum + arr[i];
}
Console.WriteLine("No subarray found");
return 0;
}
// Driver code
public static void Main()
{
GFG arraysum = new GFG();
int[] arr = new int[] { 15, 2, 4, 8, 9, 5, 10, 23 };
int n = arr.Length;
int sum = 23;
arraysum.subArraySum(arr, n, sum);
}
}
// This code has been contributed by KRV.
<script>
/* Returns true if the there is
a subarray of arr[] with sum equal to
'sum' otherwise returns false.
Also, prints the result */
function subArraySum(arr,n,sum)
{
let currentSum = arr[0], start = 0, i;
// Pick a starting point
for (i = 1; i <= n; i++) {
// If currentSum exceeds the sum,
// then remove the starting elements
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
// If currentSum becomes equal to sum,
// then return true
if (currentSum == sum) {
let p = i - 1;
document.write(
"Sum found between indexes " + start
+ " and " + p+"<br>");
return 1;
}
// Add this element to currentSum
if (i < n)
currentSum = currentSum + arr[i];
}
document.write("No subarray found");
return 0;
}
let arr=[15, 2, 4, 8, 9, 5, 10, 23 ];
let n = arr.length;
let sum = 23;
subArraySum(arr, n, sum);
// This code is contributed by unknown2108
</script>
<?php
/* An efficient program to print
subarray with sum as given sum */
/* Returns true if the there is a
subarray of arr[] with sum equal
to 'sum' otherwise returns false.
Also, prints the result */
function subArraySum($arr, $n, $sum)
{
/* Initialize currentSum as
value of first element
and starting point as 0 */
$currentSum = $arr[0];
$start = 0; $i;
/* Add elements one by one to
currentSum and if the currentSum
exceeds the sum, then remove
starting element */
for ($i = 1; $i <= $n; $i++)
{
// If currentSum exceeds the sum,
// then remove the starting elements
while ($currentSum > $sum and
$start < $i - 1)
{
$currentSum = $currentSum -
$arr[$start];
$start++;
}
// If currentSum becomes equal
// to sum, then return true
if ($currentSum == $sum)
{
echo "Sum found between indexes",
" ", $start, " ",
"and ", " ", $i - 1;
return 1;
}
// Add this element
// to currentSum
if ($i < $n)
$currentSum = $currentSum + $arr[$i];
}
// If we reach here,
// then no subarray
echo "No subarray found";
return 0;
}
// Driver Code
$arr = array(15, 2, 4, 8,
9, 5, 10, 23);
$n = count($arr);
$sum = 23;
subArraySum($arr, $n, $sum);
// This code has been
// contributed by anuj_67.
?>
Output
Sum found between indexes 1 and 4
Time Complexity: O(N)
Auxiliary Space: O(1). Since no extra space has been taken.
Find subarray with given sum using DP:
We can use dynamic programming to find the subarray with the given sum. The basic idea is to iterate through the array, keeping track of the current sum and storing the difference between the current sum and the given sum in a hash table. If the difference is seen again later in the array, then we know that the subarray with the given sum exists and we can return it. This approach is efficient in terms of time and space, but it may not be suitable if the array is very large and the hash table becomes too large to fit in memory.
Algorithm:
- Initialize an empty hash table and a variable curr_sum to 0.
- Iterate through the array, keeping track of the current element in a variable i.
- Add i to curr_sum and check if curr_sum – sum is in the hash table. If it is, then return the subarray from the index stored in the hash table to i.
- If curr_sum – sum is not in the hash table, add an entry to the hash table with the key curr_sum and the value i.
- If you reach the end of the array and no subarray with the given sum is found, return an empty array.
Below in the implementation of the above approach:
#include <iostream>
#include <unordered_map>
#include <vector>
std::vector<int> find_subarray_with_given_sum(const std::vector<int>& arr, int sum)
{
std::unordered_map<int, int> map;
int curr_sum = 0;
for (int i = 0; i < arr.size(); i++) {
curr_sum += arr[i];
if (curr_sum == sum) {
return std::vector<int>({0, i});
}
if (map.count(curr_sum - sum)) {
return std::vector<int>({map[curr_sum - sum] + 1, i});
}
map[curr_sum] = i;
}
return {};
}
int main()
{
std::vector<int> arr = {15, 2, 4, 8, 5, 10, 23};
int target_sum = 21;
std::vector<int> subarray = find_subarray_with_given_sum(arr, target_sum);
if (subarray.empty()) {
std::cout << "No subarray with sum " << target_sum << " found." << std::endl;
} else {
std::cout << "Sum found between indexes " << subarray[0] << " and " << subarray[1] << std::endl;
}
return 0;
}
import java.util.HashMap;
import java.util.Map;
public class SubarraySum {
public static int[] findSubarrayWithGivenSum(int[] arr, int sum) {
Map<Integer, Integer> map = new HashMap<>();
int currSum = 0;
for (int i = 0; i < arr.length; i++) {
currSum += arr[i];
if (currSum == sum) {
return new int[]{0, i};
}
if (map.containsKey(currSum - sum)) {
return new int[]{map.get(currSum - sum) + 1, i};
}
map.put(currSum, i);
}
return new int[]{};
}
public static void main(String[] args) {
int[] arr = {15, 2, 4, 8, 5, 10, 23};
int targetSum = 21;
int[] subarray = findSubarrayWithGivenSum(arr, targetSum);
if (subarray.length == 0) {
System.out.println("No subarray with sum " + targetSum + " found.");
} else {
System.out.println("Sum found between indexes " + subarray[0] + " and " + subarray[1]);
}
}
}
def find_subarray_with_given_sum(arr, target_sum):
curr_sum = 0
index_map = {}
for i, num in enumerate(arr):
curr_sum += num
if curr_sum == target_sum:
return [0, i]
if curr_sum - target_sum in index_map:
startIndex = index_map[curr_sum - target_sum]
#Accounting for a value of 0 at the start Index in arr
startIndex = startIndex if arr[startIndex] == 0 else startIndex + 1
return [startIndex, i]
index_map[curr_sum] = i
return []
arr = [8,2,4,0,6,9,1,2]
target_sum = 18
subarray = find_subarray_with_given_sum(arr, target_sum)
if not subarray:
print(f"No subarray with sum {target_sum} found.")
else:
print(f"Sum found between indexes {subarray[0]} and {subarray[1]}")
using System;
using System.Collections.Generic;
class SubarraySum {
static int[] FindSubarrayWithGivenSum(int[] arr, int sum) {
Dictionary<int, int> map = new Dictionary<int, int>();
int currSum = 0;
for (int i = 0; i < arr.Length; i++) {
currSum += arr[i];
if (currSum == sum) {
return new int[]{0, i};
}
if (map.ContainsKey(currSum - sum)) {
return new int[]{map[currSum - sum] + 1, i};
}
map[currSum] = i;
}
return new int[]{};
}
static void Main() {
int[] arr = {15, 2, 4, 8, 5, 10, 23};
int targetSum = 21;
int[] subarray = FindSubarrayWithGivenSum(arr, targetSum);
if (subarray.Length == 0) {
Console.WriteLine($"No subarray with sum {targetSum} found.");
} else {
Console.WriteLine($"Sum found between indexes {subarray[0]} and {subarray[1]}");
}
}
}
function findSubarrayWithGivenSum(arr, sum) {
const map = new Map();
let currSum = 0;
for (let i = 0; i < arr.length; i++) {
currSum += arr[i];
if (currSum === sum) {
return [0, i];
}
if (map.has(currSum - sum)) {
return [map.get(currSum - sum) + 1, i];
}
map.set(currSum, i);
}
return [];
}
const arr = [15, 2, 4, 8, 5, 10, 23];
const targetSum = 21;
const subarray = findSubarrayWithGivenSum(arr, targetSum);
if (subarray.length === 0) {
console.log(`No subarray with sum ${targetSum} found.`);
} else {
console.log(`Sum found between indexes ${subarray[0]} and ${subarray[1]}`);
}
Output
Sum found between indexes 0 and 2
Time Complexity: O(N)
Auxiliary Space: O(N)
The above solution doesn’t handle negative numbers. We can use hashing to handle negative numbers. See below set 2.
Contact Us