Array ( [0] => [1] => questions [2] => Strings [3] => Sub-Array--Sum )
Given an array of integers and value X. You have to find the sub array whose sum is equal to X. If it is not found print -1.
First line contains the size of the first array. Next line contains the m integers separated by the spaces. Next line contains the value X.
Print the subarray elements.
6 2 5 1 6 3 7 15
5 1 6 3
10 3 7 2 8 9 1 10 6 11 4 46
3 7 2 8 9 1 10 6
4 7 2 9 3 23
-1
Login to see Discussion
Approach1:
Step-i) Initialize a 2 dimensional matrix of size n*n array size.
Step-ii) Iterate a loop i from 0 to n.
Step-iii) Initialize a[i][i]=0.
Step-iv) Iterate other loop j from i+1 to n.
Step-v) Assign a[i][j] with sum of a[i-1][j] and a[j].
Step-vi) While finding, if any value is equal to given sum, then return it.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
Approach2:
Step-i) consider the 1st element and take it as a sub array
Step-ii) start from the 2nd element and add the elements one by one
Step-iii) if that is equal to the sum, return it
Step-iv) if the adding element > sum remove it
Step-v) If sum of the subarray elements exceeds the sum, then remove before elements while sum of the sub array elemts is greater than sum.
Time Complexity: O(n logn)
Space Complexity: O(n)
Note :
Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.
Login to see Solution