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 <[email protected]> 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 <[email protected]> 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 [email protected].
>> To unsubscribe from this group, send email to
>> [email protected]<algogeeks%[email protected]>
>> .
>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
