Make an associative sum array ... then find two indexes in the new
array such that b[j] - b[i] =k, which can be done by a hash table. The
found indexes form ur answer , i+1 & j.
For e.g
A = {1,2,3,4,5,6,7,8,9}
B = {1,3,6,10,15,21,28,36,45}
and k = 15
now B[5] - B[2] = 15
so ans is 3 & 5 i.e 4+5+6Running time O(n). Regards Aviral http://coders-stop.blogspot.com/ On Sep 2, 8:35 pm, 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.
