Take two pointers both at the start of each array... i=0,j=0 let the size of sorted arrays be m and n int func(int num,int m,int n){ int i=0,j=0; while (i<m&&j<n){ if((num<=a[i])||(num<=a[j])||num<(a[i]+b[j])) return 0; if(num==(a[i]+b[j])) return 1; if(num>a[i]+b[j]){ if(a[i]>b[j]) j++; else i++; } } return 0; }
O(m+n) complexity Ps. i'm returning true if the number equals a[i]+b[j] and not just when it equals a single element in any array On Fri, Jul 23, 2010 at 9:22 AM, Shafi Ahmad <shafi.ah...@gmail.com> wrote: > Let argument of function Func is k. > Case 1: If at least on of the array is sorted (say array1) then. > For each number in array2, do > 1. binary search for (k - array1[i]) in array1 > 2. if found > return true. > else > return false > case 2: Arrays are not sorted then > 1. Sort one array and apply algo for case 1. > > Time complexity will be sizeof(unsortedarray)log (sizeofsortedarray). > > Regards, > Shafi > On Fri, Jul 23, 2010 at 12:01 AM, vijay <auvija...@gmail.com> wrote: > >> You have 2 arrays of integer. You have to write a function, which take >> an integer as input and returns bool. Example array 1 has {1,5,10} >> array 2 has {2,5,9}. Func(3) should return true, since 1 (from array >> 1) +2 (from array 2) =3 ( i.e summation of 2 numbers (1 from each >> array) is equal to 3). Func(13) should return false >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Regards, > Shafi Ahmad > > The difficult we do immediately, the impossible takes a little longer....US > Army > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT IIIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.