we can do this without taking O(n) space .. but time is O(n^2) as in i
already mentioned where the solution is ...
On Fri, Sep 2, 2011 at 7:35 AM, Neha Singh <neha.ndelhi.1...@gmail.com>wrote:
> @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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar>
*
Mobile +91 8056127652*
<bagana.bharatku...@gmail.com>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
