@atul.. Why both 'l--' and 'm--' together ? doing this you will miss out on lot of intermediate values.. Also, if the array sorted and u want to capture the all valid values for check in the minimum runtime then instead of having 2 right pointers, have 1 left and 1 right pointer and inc/dec one of them based on the outcome..
Secondly doing K++ , at the place where you are doing it, is incorrect... K++ will hold good only when ' l--,m-- ' is a good enough way of reducing the sample space which is actually not.. If u fix the above issues, then i think your run-time will be O(n^3)... Basically the way i see, correct me if i m wrong, what u r trying to do is : In a sorted array, for all (i , k) we are trying to find 2 nos. (A[l], A[m]) whose sum is equal to e - A[i] -A[k].. given i < k < l < m .... pairs of (i, k) - O(N^2) to find a pair having sum (e- A[i] -A[k]) - O(N). Hence, O(N^3) time complexity.. On Jan 2, 8:20 am, Arun Vishwanathan <aaron.nar...@gmail.com> wrote: > does this make sense? > 1)sort array O(nlogn) > 2)keep 4 pointer to last 4 elements of array. At each point in the > algorithm we need to ensure than i<j<k<l where i j k and l are positions of > the 4 pointers. > 3)if(sum of those 4 elements < k) there exists no such combination > else > do binary search with all 4 pointers in nested loop fashion > for example if 20 elements in array , say with binary search last pointer > starts pointing to position 10. then 3rd last pointer will point to 10/2=5 > and 2nd last pointer points to 5/2 =2and first pointer points to 2/2 =1st > position. After first pointer is done with binary search, then second > pointer moves to next position according to binary search (less than > position of 3rd pointer )and then first pointer again does binary search in > this new space etc etc...basically it is something like > O(logn*logn*logn*logn)...I guess this is less than O(n^3)?? > > > > > > > > > > On Sun, Jan 1, 2012 at 10:31 AM, atul anand <atul.87fri...@gmail.com> wrote: > > sort(arr); > > min=arr[0]+arr[1]+arr[2]+arr[3]; > > max=arr[n-1]+arr[n-2]+arr[n-3]+arr[n-4]; > > > for(i=0;i<n-3;i++) > > { > > a=arr[i]; > > k=i+1; > > l=n-1; > > m=n-2; > > while(k<l) > > { > > b=arr[k]; > > c=arr[l]; > > d=arr[m]; > > if(a+b+c+d == num) > > { > > > printf("\nNumber found (%d + %d + %d + %d ) = %d",a,b,c,d,num); > > flag=1; > > break; > > } > > else if(a+b+c+d > num) > > { > > l--; > > m--; > > } > > else > > { > > k++; > > > } > > > } > > > if(flag) > > break; > > } > > > complexity = O(N^2); > > > -- > > 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. > > -- > "People often say that motivation doesn't last. Well, neither does bathing > - that's why we recommend it daily." -- 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.