Cheap and Secure Web Hosting Provider : See Now

Getting maximum number of pairs in a set

, , No Comments
Problem Detail: 

I'm sorry if the title is unclear, I didn't know how to name this question.

I have a problem where I have an array of numbers with positive integer values. For a pair of these integers to be considered valid, they should follow the format a^2 + b^2 = x^2, where a and b are the integers, and x is any whole number.

What I need to do is to find the maximum number of pairs that can be used concurrently (for example, if I have numbers {3, 4, 4}, the answer would be 1, even though there are two valid pairs (3 and the first 4, as well as 3 and the second 4), because we can not use both of these pairs at the same time.

Can anyone point me in the right direction toward solving this problem without brute-forcing all the combinations?

Asked By : Lightwind
Answered By : Yuval Filmus

Your problem is an instance of maximum matching, for which there exist efficient algorithms. The vertices in the graph are the entries of the list, and the edges correspond to allowable pairs.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56045

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback