with the inner set.
Sent from my Windows Phone
发件人: SAMMM
发送时间: 2012/1/2 1:34
收件人: Algorithm Geeks
主题: [algogeeks] Sum of Four Numbers in an Array (Amazon)
Given an array A[] and a integer num(K) . Need to find the combination
of four no's in the array whose sum is equal to num(K).
--
You re
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 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 {
> a=arr[i];
> k=i+1;
> l=n-1;
> m
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 num)
{
l--;
m--;
}
else
{
k++;
}
}
if(flag)
break;
}
complexity = O(N^2);
--
You received this message because you are subscribed to
if you want to find all combination of number which will sum to K
then change block if(a+b+c+d == num) and remove flag and break to :-
if(a+b+c+d == num)
{
printf("\nNumber found (%d + %d + %d + %d ) = %d",a,b,c,d,num);
k++;
l--;
m--;
}
--
You received this message because you are subscribed
O((n^2)*logn)
if problem is a+b+c+d=e
find all combinations of e-a-b O(N^2) as e is constant
similarly find for c+d also O(N^2)
then sort then so O((N^2)*logn)
and do a binary search for each value of e-a-b in c+d array
On Sun, Jan 1, 2012 at 11:08 PM, SAMMM wrote:
> HAPPY NEW YEAR to al
HAPPY NEW YEAR to all Geeks !!!
Given an array of size N and a integer Num(K) . Need to find the
combination of four no's in the array whose sum is equal to Num(K).
Needed a solution whose complexity is less than O(n^3) .
--
You received this message because you are subscribed to the Google Gr
Given an array A[] and a integer num(K) . Need to find the combination
of four no's in the array whose sum is equal to num(K).
--
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