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.