Continuous Subarray With Sum to S
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.
C++
#include <bits/stdc++.h>
using namespace std;
void subArraySum( int arr[], int n, int sum)
{
for ( int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
cout << "Sum found at indexes " << i << endl;
return ;
}
else {
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 ;
}
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;
}
C
#include <stdio.h>
void subArraySum( int arr[], int n, int sum)
{
for ( int i = 0; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
printf ( "Sum found at indexe %d " , i);
return ;
}
else {
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 ;
}
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;
}
Java
public class SubarraySum {
void subArraySum( int arr[], int n, int sum)
{
for ( int i = 0 ; i < n; i++) {
int currentSum = arr[i];
if (currentSum == sum) {
System.out.println( "Sum found at indexe "
+ i);
return ;
}
else {
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);
}
}
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.
C++
#include <iostream>
using namespace std;
int subArraySum( int arr[], int n, int sum)
{
int currentSum = arr[0], start = 0, i;
for (i = 1; i <= n; i++) {
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
if (currentSum == sum) {
cout << "Sum found between indexes " << start
<< " and " << i - 1;
return 1;
}
if (i < n)
currentSum = currentSum + arr[i];
}
cout << "No subarray found" ;
return 0;
}
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;
}
C
#include <stdio.h>
int subArraySum( int arr[], int n, int sum)
{
int currentSum = arr[0], start = 0, i;
for (i = 1; i <= n; i++) {
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
if (currentSum == sum) {
printf ( "Sum found between indexes %d and %d" ,
start, i - 1);
return 1;
}
if (i < n)
currentSum = currentSum + arr[i];
}
printf ( "No subarray found" );
return 0;
}
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;
}
Java
public class SubarraySum {
int subArraySum( int arr[], int n, int sum)
{
int currentSum = arr[ 0 ], start = 0 , i;
for (i = 1 ; i <= n; i++) {
while (currentSum > sum && start < i - 1 ) {
currentSum = currentSum - arr[start];
start++;
}
if (currentSum == sum) {
int p = i - 1 ;
System.out.println(
"Sum found between indexes " + start
+ " and " + p);
return 1 ;
}
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);
}
}
Python3
def subArraySum(arr, n, sum_):
currentSum = arr[ 0 ]
start = 0
i = 1
while i < = n:
while currentSum > sum_ and start < i - 1 :
currentSum = currentSum - arr[start]
start + = 1
if currentSum = = sum_:
print ( "Sum found between indexes % d and % d" % (start, i - 1 ))
return 1
if i < n:
currentSum = currentSum + arr[i]
i + = 1
print ( "No subarray found" )
return 0
if __name__ = = '__main__' :
arr = [ 15 , 2 , 4 , 8 , 9 , 5 , 10 , 23 ]
n = len (arr)
sum_ = 23
subArraySum(arr, n, sum_)
C#
using System;
class GFG {
int subArraySum( int [] arr, int n, int sum)
{
int currentSum = arr[0], start = 0, i;
for (i = 1; i <= n; i++) {
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
if (currentSum == sum) {
int p = i - 1;
Console.WriteLine( "Sum found between "
+ "indexes " + start
+ " and " + p);
return 1;
}
if (i < n)
currentSum = currentSum + arr[i];
}
Console.WriteLine( "No subarray found" );
return 0;
}
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);
}
}
PHP
<?php
function subArraySum( $arr , $n , $sum )
{
$currentSum = $arr [0];
$start = 0; $i ;
for ( $i = 1; $i <= $n ; $i ++)
{
while ( $currentSum > $sum and
$start < $i - 1)
{
$currentSum = $currentSum -
$arr [ $start ];
$start ++;
}
if ( $currentSum == $sum )
{
echo "Sum found between indexes" ,
" " , $start , " " ,
"and " , " " , $i - 1;
return 1;
}
if ( $i < $n )
$currentSum = $currentSum + $arr [ $i ];
}
echo "No subarray found" ;
return 0;
}
$arr = array (15, 2, 4, 8,
9, 5, 10, 23);
$n = count ( $arr );
$sum = 23;
subArraySum( $arr , $n , $sum );
?>
Javascript
<script>
function subArraySum(arr,n,sum)
{
let currentSum = arr[0], start = 0, i;
for (i = 1; i <= n; i++) {
while (currentSum > sum && start < i - 1) {
currentSum = currentSum - arr[start];
start++;
}
if (currentSum == sum) {
let p = i - 1;
document.write(
"Sum found between indexes " + start
+ " and " + p+ "<br>" );
return 1;
}
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);
</script>
Output
Sum found between indexes 1 and 4
Time Complexity: O(N)
Auxiliary Space: O(1). Since no extra space has been taken.
The above solution doesn't handle negative numbers. We can use hashing to handle negative numbers. See below set 2.
- Find subarray with given sum | Set 2 (Handles Negative Numbers)
- Find subarray with given sum with negatives allowed in constant space
Source: https://www.geeksforgeeks.org/find-subarray-with-given-sum/
0 Response to "Continuous Subarray With Sum to S"
Post a Comment