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?

$\endgroup$
  • 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 '16 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$ – Lightwind Apr 16 '16 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 '16 at 23:33
  • $\begingroup$ Ah, yes it is, thank you. I am new here, can I mark your comment as the answer somehow? $\endgroup$ – Lightwind Apr 16 '16 at 23:40
  • $\begingroup$ Later on I or someone else will write it as an actual answer. $\endgroup$ – Yuval Filmus Apr 16 '16 at 23:42
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.