we have to consider 3 cases ..
1) that sub array can be in first half
2) that sub array can be in second half
3) that sub array can be in middle .
On Fri, Sep 2, 2011 at 7:56 AM, bharatkumar bagana <
bagana.bharatku...@gmail.com> wrote:
> 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>
>
>
>
--
**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.
