@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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
