@atul..
Yes,
j=K and p=4....
Also would like to mention that in my first post I have mentioned
about a variable 'R' and not used it in the explanation..
Actually 'R' is nothing but 'p', in case you got confused...
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.
