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.
