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.comwrote:
@anoop
when you find some i and j(i j) meet the condition i.e. asq[i] + asq[j]
== asq[k], you can merge
@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
@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)
@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:
