wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Right angle Triangle Problem
        
(Message started by: sumtatt on Jan 10^th, 2012, 5:44am)

Title: Right angle Triangle Problem
Post by sumtatt on Jan 10^th, 2012, 5:44am

There is array of some number of integers, find the combination of all number which make the right angle triangle.
i.e
int a[9] = (1,2,3,4,5,6,7,8,10);

Answer should be (3,4,5) (6,8,10)

Kindly provide the link if it has already asked.

Title: Re: Rectangle Triangle Problem
Post by Grimbal on Jan 10^th, 2012, 6:49am

I don't understand what you mean by "make the rectangle triangle.
Also, in your output there is a 5, which is not in the input. Is that normal?

Title: Re: Rectangle Triangle Problem
Post by towr on Jan 10^th, 2012, 8:37am

I think he means Pythagorean triangles.

Title: Re: Rectangle Triangle Problem
Post by Grimbal on Jan 10^th, 2012, 9:46am

Makes sense.

One method would be to take every pair in the set as the first 2 numbers and do a binary search for the third.

Another method would be to generate all triples up to the maximum number in the set and check each triple if it's in the set.

The first method would be best if the numbers are few and very large. The second if the numbers are many and relatively small.

Title: Re: Rectangle Triangle Problem
Post by sumtatt on Jan 10^th, 2012, 11:29am

Thanks!

What will be the complexity for the same.

Can you write the algorithm please?

Title: Re: Rectangle Triangle Problem
Post by sumtatt on Jan 10^th, 2012, 11:32am

Sorry Grimbal.. I have corrected the question.
I think i have lost my mind when i was writing.
My apologies.