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 < [email protected]> 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 <[email protected]>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 [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. >> > > > > -- > > **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* > <[email protected]> > > > -- **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* <[email protected]> -- 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.
