Find four elements a, b, c and d in an array such that a+b = c+d - GeeksforGeeks

Find four elements a, b, c and d in an array such that a+b = c+d - GeeksforGeeks

Find four elements a, b, c and d in an array such that a+b = c+d

Given an array of distinct integers, find if there are two pairs (a, b) and (c, d) such that a+b = c+d, and a, b, c and d are distinct elements. If there are multiple answers, then print any of them.

Example:

Input:   {3, 4, 7, 1, 2, 9, 8}  Output:  (3, 8) and (4, 7)  Explanation: 3+8 = 4+7    Input:   {3, 4, 7, 1, 12, 9};  Output:  (4, 12) and (7, 9)  Explanation: 4+12 = 7+9    Input:  {65, 30, 7, 90, 1, 9, 8};  Output:  No pairs found  

Expected Time Complexity: O(n²)

We strongly recommend you to minimize your browser and try this yourself first.

A Simple Solution is to run four loops to generate all possible quadruples of array element. For every quadruple (a, b, c, d), check if (a+b) = (c+d). Time complexity of this solution is O(n⁴).

An Efficient Solution can solve this problem in O(n²) time. The idea is to use hashing. We use sum as key and pair as value in hash table.

Read full article from Find four elements a, b, c and d in an array such that a+b = c+d - GeeksforGeeks