Home » Subarray with given sum

Subarray with given sum

by Online Tutorials Library

Subarray with given sum

  • In this problem, we are provided with an unsorted array of non-negative integers and a sum integer value.
  • We need to find the part from the array, or can we need to find the Subarray, in which the sum of the elements of that array is exactly matched to the given sum.
  • We need to apply the algorithm to solve this problem, which ultimately results in the desired output.

Let us try to understand it with the help of an example –

We are given an array and a sum.

Example 1 :

Given:

arr = { 10 , 12 , 2 , 4 , 13 , 19 , 5 }

sum = 18

Output :

The given sum is found from indexes 1 to 3

And the subarray is: { 12 , 2 , 4 }

Required sum between indexes of corresponding elements are : 12 + 2 + 4 = 18

Example 2 :

Given:

arr = { 1 , 12 , 2 , 14 , 3 , 16 , 4 }

sum = 19

Output :

The given sum is found from indexes 4 to 5

And the Subarray is: { 3, 16 }

Required sum between indexes of corresponding elements are : 3 + 16 = 19

Example 3 :

Given:

arr = { 1 , 12 , 2 , 14 , 3 , 16 , 4 }

sum = 5

Output :

The given sum is not found in the given array

Example 4 :

Given:

arr = { 1 , 13 , 2 , 14 , 3 , 7 , 4 }

sum = 14

Output :

The given sum is found from indexes 0 to 1

And the Subarray is: { 1, 13 }

Required sum between indexes of corresponding elements are : 1 + 13 = 14

Here if we observe that, we have more than one Subarray, in which the sum of all elements is equal to 14, i.e., are as follows –

  1. First subarray is found from indexes 0 to 1, i.e., { 1 , 13 }.
  2. Second subarray is found on index 3, i.e., { 14 }.
  3. The third Subarray is found from indexes 4 to 6, i.e., { 3, 7, 4 }.

What is the output if we get multiple such sub-arrays producing the desired sum by adding their elements?

It will display the first shortest Subarray, whose sum of elements exactly matches the given sum. We are deriving the algorithm based on the above logic; in short, we are finding the sub-array that matches the corresponding given sum at the very first time.

Methods to Solve the Problem for finding the Subarray from the given array, whose sum of elements matches with the given sum –

  1. To use the Brute force approach, an inefficient and simple method.
  2. To use the Linear complexity method, an efficient approach.

Let us find the Subarray from the given array, whose sum matches the given sum using these methods mentioned above.

Method # 1 Brute Force approach, an inefficient and simple method –

The method a programmer must prefer is always brute force approach, which will increase our understanding of the problem. Once we have solved this problem using this method, it will lead to raising our confidence level, and after then we can go further to try with the other methods, which is probably more efficient then this method.

Let us discuss the above problem using this method:

As we have already seen, the working of this problem, we all need to find a subarray in which the sum of all elements matches with the given sum value.

Algorithm to implement Brute force approach to solve this problem –

Step 1 – Take an array from the user of ‘ n ‘ elements; which refer to the non-negative integers in the main function. We can also take the sum value from the user to generate the result accordingly.

Step 2 – Make a function call to find a subarray in which the sum of all the elements matches the given sum. Pass the original array, number of elements, and given sum value in the function as an argument.

Step 3 – In a Subarray function, run two loops; one loop will run from the 0th index of the array to the last index. We can define i = 0 to i = n-1 to traverse the array from index 0 to the last index.

Step 4 – Another loop is inside the first loop, as we can say nested loop, and it will run from j = i + 1 to n.

Step 5 – At the starting of this subarray function, declare a variable named currentsum; which will initially be initialized with arr [ 0 ].

Step 6 – In the second loop, derive the condition to check whether the current sum is equal to the given sum or not; if it equals, then print the result in the form of indexes.

Step 7 – If not, check if the currentsum is greater than the sum of j == n or not; if this condition is true, break from the loop.

Step 8 – Finally assign currentsum = currentsum + arr [ j ].

Step 9 – Step 8 will calculate the current sum by incrementing the value of currentsum by adding the value present at index j if the conditions of currentsum == sum fail.

Step 10 – After executing loop1 and nested loop2 inside loop1, we will get the desired result.

Step 11 – If a still case arises where the currentsum does not match the given sum, it indicates that no such subarray exists in the main array.

Step 12 – Finally, we will get the desired output, as a result, on the screen.

Implementation of Subarray with given sum Problem using Method # 1 in C Programming Language

The output of the following C program for solving the Subarray with given sum problem using Method # 1

subarray with given sum

Implementation of Subarray with given sum Problem using Method # 1 in C++ Programming Language

The output of the following C++ program for solving the Subarray with given sum problem using Method # 1

subarray with given sum

Implementation of Subarray with given sum Problem using Method # 1 in Python Programming Language

The output of the following Python program for solving the Subarray with given sum problem using Method # 1

subarray with given sum

Implementation of Subarray with given sum Problem using Method # 1 in Java Programming Language

The output of the following Java program for solving the Subarray with given sum problem using Method # 1

subarray with given sum

Implementation of Subarray with given sum Problem using Method # 1 in C# Programming Language

The output of the following C# program for solving the Subarray with given sum problem using Method # 1

subarray with given sum

After executing the program successfully in a specific programming language and following the Brute force algorithm using the double traversal approach, we will get the proper result, i.e., finding the resultant Subarray, whose sum of elements is exactly equal to the given sum value.

Now let us analyze the running time and performance of the algorithm we are applying to sort the array in ascending order by finding the algorithm’s time complexity and space complexity using in Method # 1.

Time Complexity of Method # 1 –

For finding the time complexity, we need to observe the algorithm and analyze the time taken by a particular line for execution. We can observe that we require traversing the array using two for loops and checking the condition for finding the sum. Hence time complexity will be –

T ( n ) = O ( n ).O ( n )

T ( n ) = O ( n2 )

Hence time complexity will be O ( n2 ), as we do the asymptotically rough idea that we require ‘ n2 ‘ time to solve the problem of ‘ n ‘ elements.

Space Complexity of Method # 1 –

To find space complexity, we need to observe the program and analyze the space required to store all the variables; as we notice the program, we will observe that no extra space is required to store the elements.

S ( n ) = O ( 1 )

Hence the space complexity for above method # 1 will be constant.

Method # 2 Linear Complexity method, an inefficient and simple approach –

As we have already seen the working of method 1, i.e., Brute force approach, we will move further towards a more efficient method; it is very easy to implement to solve any problem; as the name suggests, the linear complexity method has linear complexity. Once you have succeeded in making the program, try to find the other best alternative to solve the given problem, in a much more efficient way, whose performance is better and time complexity is less than this method.

Let us discuss the above problem using this method:

As we have already seen, the working of this problem, we all need to find a subarray in which the sum of all elements matches with the given sum value.

Algorithm to implement Linear complexity method to solve this problem –

Step 1 – Take an array from the user of ‘ n ‘ elements; elements refer to the non-negative integers in the main function. Also, take the sum value from the user so that we can generate the result accordingly.

Step 2 – Make a function call to find a subarray in which the sum of all the elements matches the given sum. Pass the original array, number of elements, and given sum value in the function as an argument.

Step 3 – In a Subarray function, run one loop only; it will run from the 0th index of the array to the last index. We can define i = 0 to i = n-1 to traverse the array from index 0 to the last index. Also, assign a variable named ‘ begin ‘ with 0.

Step 4 – At the starting of this subarray function, declare a variable named currentsum; this variable will initially be initialized with arr [ 0 ].

Step 5 – Inside that loop, we will run a while loop to check the condition whether the currentsum is greater than the given sum, and begin is less than i – 1; if this condition is true, then we will update the current sum variable as current sum – arr [ begin ], after then increment begin as begin = begin + 1.

Step 6 – After that, out from the while loop, check the condition using if statement as, whether currentsum equals sum or not.

Step 7 – If true, print the result as the sum between the indexes, begin, and i – 1.

Step 8 – After then check one more statement using the if statement, whether i is less than n or not.

Step 9 – If proved true, update the currentsum with currentsum + arr [ i ].

Step 10 – If a still case arises where the currentsum does not match the given sum, it indicates that no such subarray exists in the main array.

Step 11 – Finally, we will get the desired output, as a result, on the screen.

Implementation of Subarray with given sum Problem using Method # 2 in C Programming Language

The output of the following C program for solving the Subarray with given sum problem using Method # 2

subarray with given sum

Implementation of Subarray with given sum Problem using Method # 2 in C++ Programming Language

The output of the following C++ program for solving the Subarray with given sum problem using Method # 2

subarray with given sum

Implementation of Subarray with given sum Problem using Method # 2 in Java Programming Language

The output of the following Java program for solving the Subarray with given sum problem using Method # 2

subarray with given sum

Implementation of Subarray with given sum Problem using Method # 2 in Python Programming Language

The output of the following Python program for solving the Subarray with given sum problem using Method # 2

subarray with given sum

Implementation of Subarray with given sum Problem using Method # 2 in C# Programming Language

The output of the following C# program for solving the Subarray with given sum problem using Method # 2

subarray with given sum

Now let us analyze the performance and running time of the algorithm we are applying to find a subarray in which the sum of its elements is equal to the given sum value by finding the algorithm’s time complexity and space complexity using in Method # 2.

Time Complexity of Method # 2 –

For finding the time complexity, first, we need to observe the algorithm and analyze the time taken by a particular line of code for execution. We can observe that traversing of an array is done by using only one for loop and checking the condition for finding the sum. Hence time complexity will be –

T ( n ) = O ( n ) + C

Here, ‘ C ‘ be any constant

T ( n ) = O ( n )

Hence time complexity will be O ( n ), as we do the asymptotically rough idea that we require ‘ n ‘ time to solve the problem of ‘ n ‘ elements.

Space Complexity of Method # 2 –

To find space complexity, we need to observe the lines of code and analyze the space required to store all the variables, as we notice the program that no extra space is required to store the elements.

S ( n ) = O ( 1 )

Hence the space complexity for above method # 2 will be constant.


You may also like