I need to find a fast algorithm to perform this task. Possible O(n log n) or even O(n).

For example, giving following 5 arrays:
$\begin{bmatrix}1, 2,3,4,5\end{bmatrix}$
Result should be 6.

I think of an idea using inclusion-exclusion but I am not sure.

EDIT: array can will be small enough to negligible


put on hold as unclear what you're asking by Evil, Hendrik Jan, David Richerby, Discrete lizard, Juho 2 days ago

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What have you tried? Whede did you get stuck? Could pairs be reused? $\endgroup$ – Evil Jan 5 at 2:59
  • $\begingroup$ Only thing I have thought is brute force which too slow. I had idea of graph theory algorithm but still does not go fast enough. I tried using graph theory but still not fast. I do not know what you mean by reused but (0, 1)is same as(1, 0). @Evil Thank you for your help $\endgroup$ – user98580 Jan 5 at 3:04
  • $\begingroup$ What if you sort them, does it get easier? In your case n = 25? Are arrays equal in length? Integers only? Bounded? Could you share more details? Where did you find this problem? Could you attribute source? $\endgroup$ – Evil Jan 5 at 3:17
  • 4
    $\begingroup$ Please credit the original source of the problem. Please relieve our concern that this might be a problem of an ongoing programming contest. $\endgroup$ – Apass.Jack Jan 5 at 7:37

Browse other questions tagged or ask your own question.