Sub-array with given sum in C++

April 13, 2023

Sub-array with given sum

Here, in this page we will write the program for sub-array with given sum in C++ . Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Sub-arrays having their sum equal to the given integer . We will understand this problem in detail with algorithm and code in C++

sub-array with given sum

Sub-Array With Given Sum in C++

A Sub-array with given sum code in C++ is a program that  to a contiguous subsequence of elements within an array that has a sum equal to a specific target value. In other words, it is a consecutive sequence of elements in an array whose sum is equal to a given sum value. The goal is to find such a sub-array within the given array.

Example : arr[ ] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output : Sum found between indexes 1 and 4 Sum of elements between indices 1 and 4 is (4 + 0 + 0 + 3) = 7

On this page we will discuss two different methods for this-

  1. Naive Approach
  2. Sliding Window Approach
Sub-array with given sum
  1. Naive approach: The naive approach to find a sub-array with a given sum in C++ involves using a nested loop to check all possible sub-arrays of the given array. For each starting index ‘i’, it checks all sub-arrays starting from ‘i’ and ending at ‘j’, and calculates their sum. If the sum matches the given sum, it prints the indices of the sub-array and returns. If no -with the sum is found, it prints a message indicating the absence of such a sub-array.

Algorithm:

  1. Take the input array arr and target sum sum as input.
  2. Initialize curr_sum to 0.
  3. Traverse the array arr from the first element to the last element with a loop variable i ranging from 0 to n-1, where n is the length of the array.
  4. For each i:
    1. Initialize curr_sum as arr[i].
    2. Traverse the array arr from i+1 to n with a loop variable j ranging from i+1 to n-1.
    3. For each j:
      1. Add arr[j] to curr_sum.
      2. If curr_sum is equal to the target sum, print the starting and ending indices of the sub-array as “Subarray found between indexes i and j” and return.
      3. If curr_sum is greater than the target sum or j is equal to n-1, break out of the loop and continue with the next element i.
  5. If no sub-array is found, print “No sub-array found”.
DSA desktop gif
DSA mobile gif

Given an array which consists of only 0, 1
Move all the negative elements to one side of the array

Minimum no. of Jumps to reach the end of an array 

Find Largest sum contiguous Subarray

Minimize the maximum difference between heights 

C++ code for Naive Approach

Run 
#include <iostream>
#include <vector>

void findSubarray (std::vector < int >&arr, int sum)
{
  int n = arr.size ();
  for (int i = 0; i < n; i++)
    {
      int curr_sum = 0;

      for (int j = i; j < n; j++)
	{
	  curr_sum += arr[j];

	  if (curr_sum == sum)
	    {
	      std::
		cout << "Subarray found between indexes " << i << " and " << j
		<< std::endl;
	      return;
	    }
	}
    }

  std::cout << "No subarray found" << std::endl;
}

int main ()
{
  std::vector < int >arr = { 15, 2, 4, 8, 9, 5, 10, 23 };
  int sum = 23;

  findSubarray (arr, sum);

  return 0;
}

Output

Subarray found between indexes 1 and 4
  1. Sliding Window approach:The code uses a sliding window approach to search for a sub-array with a given sum. The window, represented by the variables ‘start’ and ‘i’, is moved from the left to the right of the array while maintaining a running sum ‘curr_sum’. If the current sum matches the target sum, the indices of the sub-array are printed. If no sub-array with the sum is found, a message indicating the absence of such a sub-array is printed.

Algorithm:

  1. Take the input array arr and target sum sum as input.
  2. Initialize two variables, start and curr_sum, to the first element of the array, i.e., arr[0].
  3. Traverse the array arr from the second element to the last element with a loop variable i ranging from 1 to n-1, where n is the length of the array.
  4. For each i:
    1. Check if curr_sum is greater than the target sum.
    2. If so, increment start by 1 and subtract arr[start-1] from curr_sum until curr_sum is less than or equal to the target sum.
    3. If curr_sum is equal to the target sum, print the starting and ending indices of the subarray as “Subarray found between indexes start and i” and return.
    4. If curr_sum is less than the target sum and i is less than n, add arr[i] to curr_sum and continue with the next element i.
  5. If no subarray is found, print “No subarray found”.

C++ Code for sliding window approach

Run 
#include <iostream>
using namespace std;

void findSubarray (int arr[], int n, int sum)
{
  int curr_sum = arr[0];
  int start = 0;

  for (int i = 1; i <= n; i++)
    {
      while (curr_sum > sum && start < i - 1)
	{
	  curr_sum = curr_sum - arr[start];
	  start++;
	}

      if (curr_sum == sum)
	{
	  cout << "Subarray found between indexes " << start << " and " << i - 1;
	  cout << endl;
	  return;
	}

      if (i < n)
	curr_sum = curr_sum + arr[i];
    }

  cout << "No subarray found" << endl;
}

int main ()
{
  int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
  int n = sizeof (arr) / sizeof (arr[0]);
  int sum = 23;

  findSubarray (arr, n, sum);

  return 0;
}

Output

Subarray found between indexes 1 and 4

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Arrays

  • Introduction to Arrays – C | C++ | Java
  • Introduction to 2-D Arrays – C | C++ | Java
  • Sorting of Array – C | C++ | Java
  • Array Rotation – C | C++ | Java
  • Reverse an array or string- C | C++ | Java
  • Find pairs in array with given sum – C | C++ | Java
  • Sort the array in Waveform – C | C++ | Java
  • Majority Element in Array – C | C++ | Java
  • Boyer-Moore’s Voting Algorithm – C | C++ | Java
  • K-pairs with smallest sum in 2 arrays – C | C++ | Java
  • Largest Sum Contigous SubArray – C | C++ | Java
  • Maximum Average Sub-array of K length – C | C++ | Java
  • Size of sub-array with max sum – C | C++ | Java
  • Sub-array with given sum – C | C++ | Java
  • Triplet that sum to a given value – C | C++ | Java
  • Segregate 0’s and 1’s in array – C | C++ | Java
  • Segregate 0’s 1’s and 2’s in array – C | C++ | Java
  • Sort elements in array by frequency – C | C++ | Java
  • Finding pythagorean triplets in an array – C | C++ | Java
  • Reorder array using given indexes – C | C++ | Java
  • Merging two sorted arrays – C | C++ | Java
  • Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
  • Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java