Algo
loop down array find 2 elements such that c= sqrt(a*a + b*b)
& compare if( c*c ==a*a+b*b) //can be optimized we can leave this line
just writing fro clarification if yes prints all the combination
For This I Have A Gud Working Solution which has time complexity of
O(n^2)
Lets genralize
@DEV,your idea is nice.but i think it wont work in case the array is
having repeated elementsam i right
On Wed, Dec 1, 2010 at 1:51 PM, nishaanth wrote:
> I have a O(n^2) solution..
>
> Hash all the squares.0(n)
>
> Now for every pair find the sum, see if its there in the hash t
I have a O(n^2) solution..
Hash all the squares.0(n)
Now for every pair find the sum, see if its there in the hash table.O(n^2)
Total complexity : O(n^2)
On Wed, Dec 1, 2010 at 11:00 PM, fenghuang wrote:
> yeah, you're right. thank you and is it the optimal solution about this
> questio
yeah, you're right. thank you and is it the optimal solution about this
question?
On Thu, Dec 2, 2010 at 1:08 AM, Dave wrote:
> @Fenghuang: No. You don't have to search for b for every a, or more
> precisely, you don't have to search for a j for every i. Something
> like this should work for s
@Fenghuang: No. You don't have to search for b for every a, or more
precisely, you don't have to search for a j for every i. Something
like this should work for step 3:
i = 0
j = k-1
repeat while i <= j
if asq[i] + asq[j] < asq[k] then i = i+1
else if asq[i] + asq[j] > asq[k] then j = j-1
