CODEWITHSUNDEEP
algorithm
Saeed Amiri
Saeed Amiri

Reputation: 22555

Break time, find any triple which matches pythagoras equation in O(n^2)

I think it's interesting to solve this in holiday:

Given n integers, all of them within 1..n^3, find if there is a triple which matches pythagoras equation in O(n^2).

As you know pythagoras equation is a^2 + b^2 = c^2. for example 3^2 + 4^2 = 5^2.

As you know O(n^2 log n) is easy (with a little thinking), but will help to solve O(n^2). (space is not important).

Edit: As yi_H offered there is lookup table which can solve this problem easily, but for making it harder, space limit is O(n^2).

Upvotes: 1

Views: 332

Answers (3)

the guy formerly known as d
the guy formerly known as d

Reputation: 614

O(n2) time, O(n) space: square all array elements, sort, for each z in the array use the classic linear-time algorithm to determine whether there exist x, y in the array such that x + y = z.

Upvotes: 4

ypercubeᵀᴹ
ypercubeᵀᴹ

Reputation: 115530

All pythagorean triplets (a,b,c) have the following relation:

a = d * (2 * m * n)
b = d * (m^2 - n^2) 
c = d * (m^2 + n^2)

where

d >= 1  and  (m,n) = 1

(meaning: m and n have no comomn factor.

I guess one can find an algorithm to produce all triplets that are below n^3 using this info.

Upvotes: 4

Karoly Horvath
Karoly Horvath

Reputation: 96258

I guess O(n^2 log n) would be to sort the numbers, take any two pairs (O(n^2)) and see whether there is c in the number for which c^2 = a^2 + b^2. You can do the lookup for c with binary search, that's O(log(n)).

Now if space isn't an issue you can create a hash for all the values in O(n), then you can look up c in this hash with O(1), so it's going to be O(n^2). You can even create an lookup table for it since the numbers are between 1..n^2, so it's going to be a guaranteed O(1) lookup ;) You can also use a special lookup table which can do initialization, add and lookup in O(1).

Upvotes: 3

Related Questions