1
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ When can pairs be used "concurrently"? Presumably what you are really looking for is a subset of the array in which every two numbers satisfy your condition. If this is indeed the case, this is an instance of the maximum clique problem, which in general is very difficult. Of course, your particular case might be easier. $\endgroup$
    – Yuval Filmus
    Apr 16, 2016 at 22:41
  • $\begingroup$ What I mean by concurrently is that they do not overlap (for instance, in the case {3, 4, 4}, I can use either 3 and the first 4 or 3 and the second 4, not both at the same time. What I need to do is to find the configuration in which as many of the numbers will be used as possible $\endgroup$
    – user49659
    Apr 16, 2016 at 23:31
  • 1
    $\begingroup$ You should edit your question to reflect that. Your problem is an instance of maximum matching, which is efficiently solvable. Look it up. $\endgroup$
    – Yuval Filmus
    Apr 16, 2016 at 23:33
  • $\begingroup$ Ah, yes it is, thank you. I am new here, can I mark your comment as the answer somehow? $\endgroup$
    – user49659
    Apr 16, 2016 at 23:40
  • $\begingroup$ Later on I or someone else will write it as an actual answer. $\endgroup$
    – Yuval Filmus
    Apr 16, 2016 at 23:42

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.