Re: [algogeeks] Sum of Four Numbers in an Array (Amazon)

2012-01-01 Thread atul anand
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 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.



Re: [algogeeks] Sum of Four Numbers in an Array (Amazon)

2012-01-01 Thread atul anand
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;in-3;i++)
{
 a=arr[i];
 k=i+1;
 l=n-1;
 m=n-2;
 while(kl)
 {
  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.



Re: [algogeeks] Sum of Four Numbers in an Array (Amazon)

2012-01-01 Thread Arun Vishwanathan
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 ijkl 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;in-3;i++)
 {
  a=arr[i];
  k=i+1;
  l=n-1;
  m=n-2;
  while(kl)
  {
   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.