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 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
@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 wrote:
> @fenghuang try this array:
> a[]={3,3,3,3,3,3,4,4,4,4,4,4,5}
> so as
@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
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 'i
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..
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
should it be O(n^2*lgn)? for each x in n, it's O(n), and for each a,
it'sO(n), and searching b, it's O(lgn), so it's O(n*n*lgn),Thank You!
On Wed, Dec 1, 2010 at 11:02 PM, Senthilnathan Maadasamy <
senthilnathan.maadas...@gmail.com> wrote:
> Hi,
> How about the following approach?
>
> Step
Hi,
How about the following approach?
Step 1: Replace each array element with its square - O(n)
Step 2: Sort the array - O(n*log(n))
Step 3: For each element x in the array
Find two elements a, b in the array (if any) such that
a+b = x.
Since finding
If you store the squares of elements in a hash table, you dont need a binary
search reducing the running time by a factor of log_base2(n)
On Wed, Dec 1, 2010 at 12:50 AM, Akash Agrawal wrote:
> Guys,
>
> I have written a blog post for finding triplets in an integer array A[]
> which satisfy fol
Guys,
I have written a blog post for finding triplets in an integer array A[]
which satisfy following condition:
a[i]^2 + a[j]^2 = a[k]^2
http://tech-queries.blogspot.com/2010/12/finding-triplets-in-integer-array.html
I believe that more optimization are possible. It will be very helpful if
one
10 matches
Mail list logo
