Find the largest ceil(sqrt(n)) elements of A and B using a sliding window in
time O(n) and then take their cross in time sqrt(n)^2 ie O(n).
--Shambo
On Mon, Jul 11, 2011 at 12:37 PM, surender sanke <surend...@gmail.com>wrote:
> Hi, here i maintained two pair of indexes with respect to a and b, reply if
> u found any test case which fails..
>
> int npairs()
> {
> int a[] = {0,1,4,5,9,11,20};
> int b[] = {0,2,3,6,8,11,15};
> int c[20];
> int len = sizeof(a)/sizeof(a[0]);
> int i1,j1,i2,j2;
> i1=len-1;
> j1=len-2;
> i2=len-2;
> j2=len-1;
>
> int count = 0;
> c[count++] = a[len-1]+b[len-1]; //obvious
> while(count<=len)
> {
> if( (a[i1-1]+a[j2-1] > a[i1]+b[j1]) && (a[i1-1]+a[j2-1] > a[i1]+b[j1]) )
> {
> c[count++] = a[i1-1]+b[j2-1]; //highest sum with higher numbers
> have exhausted
> i1 = i1-1,j2=j2-1,j1=j2-1,i2=i1-1;
> continue;
> }
> if(a[i1]+b[j1] >= a[i2]+b[j2] )
> {
> c[count++] = a[i1]+b[j1];
> j1--;
> }
> else
> {
> c[count++] = a[i2]+b[j2];
> i2--;
> }
> }
>
> for(int i =0;i<len;i++)
> printf("%d ",c[i]);
> return 0;
> }
>
> surender
> On Mon, Jul 11, 2011 at 10:46 AM, sunny agrawal
> <sunny816.i...@gmail.com>wrote:
>
>> A = 0, 1, 4, 5, 9, 11, 20
>> B = 0, 2, 3, 6, 8, 13, 15
>>
>> (20, 15) (20, 15) -> (20,15)
>> (20,13) (11,15) -> (20,13)
>> (20,8) (11,15) -> (20,8)
>> (20,6) (11,15) -> assume (20,6)
>> (20,3) (11,15) -> (11,15)
>> (20,3) (9,15) -> (9,15)
>> (20,3) (5,15) -> (20,3) .....problem (11,13) has higher value but
>>
>> did i missed something ??
>>
>>
>> --
>> Sunny Aggrawal
>> B-Tech IV year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
