Hi,
suppose we have given n distinct numbers are a[n].
1. sort them using quick or any other sort in O(nlogn)
2. use then
int find(int *arr, int n) /* return largest number if fing it otheriwse
retirn 0*/
{
int i,j,k, temp;
for(k=n-1; k>2;k--)
{
j = k-1
i=0;
while(i!=j)
{
temp = arr[i]+arr[j];
if(temp== arr[k])
return arr[k];
else if(temp<arr[k])
i++;
else
j--;
}
}
return 0;
}
--
Thanks & Regards
Umesh kewat
Hyderabad
On Thu, Jul 15, 2010 at 9:07 AM, Ashish Goel <[email protected]> wrote:
> sort using counting sort or quickselect
>
> now a and b are less than c
>
> so find c first
> suppose c's index is k
> the start two indexes i=0 and j=k-1, if a[i]+a[j] ==a[k] return these
> numbers, else add elements at i,j if the sum is greater than c reduce j, if
> less than c increase i
>
> alternatively sort array, find index of c, make a BST or a hash table,
> starting from index 0 of the sorted array, find c-a....this is overhead on
> second thoughts, i will proceed with first approach
>
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
>
> On Wed, Jul 14, 2010 at 9:55 PM, siddharth shankar <
> [email protected]> wrote:
>
>> O ( n^2 ) soln can be done ....
>> step :
>>
>> 1 . sort array in n*log(n) .
>> 2. for every "C" from last find two number A & B such that A+B=C ... O(
>> n^2 )
>> Total :- O(N^2)
>>
>> can we improve it further ?? .... any help please ....
>>
>> On Wed, Jul 14, 2010 at 10:57 AM, Debajyoti Sarma <
>> [email protected]> wrote:
>>
>>> An array contains the set of positive integer. Find the largest number
>>> c such that c=a+b where a,b,c are distinct number of the set?
>>> [Consider , reducing complexity]
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> siddharth shankar
>>
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
