@Shashank : I think the sub array need not start from the the index 0. For
eg: If the array is of size 10, then the sub array can be from index 3 to 7.
Here is my solution :
Given : int arr[size] , int sum
1. Take an array prefix_sum[size]
2. int temp=0;prefix_sum[0]=0;
for(int i=0;i<size;i++)
{
temp+=arr[i];
prefix_sum[i]=temp;
}
3. for (int i=0;i<size;i++)
for(int j=0;j<=i;j++)
{
if(prefix_sum[i]-prefix_sum[j]+arr[j] == sum)
printf("%d %d",i,j); // sub array from index i to j is the
required sub array
}
Time : O(n^2)
Space : O(n)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
