Thanks everyone; that O(n^2) is an awesome solution.
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Thu, Dec 2, 2010 at 12:21 PM, fenghuang <fenghaungyuyi...@gmail.com>wrote:
> @anoop
> when you find some i and j(i < j) meet the condition i.e. asq[i] + asq[j]
> == asq[k], you can merge the same value without rollback.
> in this sense, you are right.
>
> On Thu, Dec 2, 2010 at 2:26 PM, anoop chaurasiya <
> anoopchaurasi...@gmail.com> wrote:
>
>> @fenghuang try this array:
>> a[]={3,3,3,3,3,3,4,4,4,4,4,4,5}
>> so asq[]={9,9,9,9,9,9,16,16,16,16,16,16,25}
>> here as u can see the total number of requisite triple pairs are 6*6=36,
>> in general for above array total number of pairs is (n/2)*(n/2) i.e. n^2/4
>> where n is the size of the array.
>> by using O(n) algo and since you are choosing them one by one,u can't
>> include all of them as they are of order O(n^2).
>> so removing repetitions is the only option i think..
>>
>> On Wed, Dec 1, 2010 at 11:37 PM, fenghuang <fenghaungyuyi...@gmail.com>wrote:
>>
>>> @anoop
>>> in fact, it always work even if there are repeated elements, because they
>>> don't change the decision.
>>> in detail, assume ii, ,jj, kk is one of the answers, then
>>> a[ii]+a[jj]=a[kk]. since the array is sorted, so a[ii-1]+a[jj] <= a[kk] and
>>> a[ii] + a[jj+1] >= a[kk].
>>> so when you try the pair of 'ii-1' and 'jj', the next step must be
>>> calculate a[ii] + a[jj] as long as a[ii-1]+a[jj] is not equal to a[kk]. the
>>> same to the pair 'ii' and 'jj+1'.
>>> the algorithm is correct and in the whole procedure, repeated elements
>>> don't affect the decision.
>>> I'm sorry for my poor English.
>>> Thank You!
>>>
>>> On Thu, Dec 2, 2010 at 12:14 PM, anoop chaurasiya <
>>> anoopchaurasi...@gmail.com> wrote:
>>>
>>>> sorry for the interruption,we can make it work even if the elements are
>>>> repeated, by removing the duplicacy in linear time(as the array is already
>>>> sorted) and taking a count of no. of duplicates in the seperate array.
>>>>
>>>> On Wed, Dec 1, 2010 at 9:37 PM, Senthilnathan Maadasamy <
>>>> senthilnathan.maadas...@gmail.com> wrote:
>>>>
>>>>> A small correction to the algorithm above. In Step 3, instead of
>>>>> finding *any* pair (a,b) such that a+b = x we need to find *all* such
>>>>> pairs. However the complexity remains the same.
>>>>>
>>>>> --
>>>>> 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.
>>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Anoop Chaurasiya
>>>> CSE (2008-2012)
>>>> NIT DGP
>>>>
>>>> --
>>>> 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.
>>>>
>>>
>>> --
>>> 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.
>>>
>>
>>
>>
>> --
>> Anoop Chaurasiya
>> CSE (2008-2012)
>> NIT DGP
>>
>> --
>> 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.
>>
>
> --
> 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.
>
--
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.
