Equal Pairs

Posted: 12 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

You are given an array of integers ARR[]. Your task is to find the index of values that satisfy X + Y = Z + W, where X, Y, Z, and W are integer values in the array.

Example
If the given array ARR = {1,19,3,17,4,5,2,18} we can see that 1+19=2+18 and 1+19 = 3+17 but we will return indices which is lexicographically smaller so answer will be {0,1,2,3}.
Note:
You have to return the indices of the elements in the given order for example you have indices like i1,i2,i3,i4 so that i1 < i2 and i3 < i4, i1 < i3, i2 != i3 and i2 != i4.

If there is more than one solution, then return the pairs of indices that are lexicographically smallest.

Suppose you have two solutions S1 = i1, i2, i3, i4, and S2 = j1, j2, j3, j4 then S1 is lexicographically smaller than S2 if and only if i1 < j1 and if i1 = j1 then i2 < j2 and if i2=j2 then i3 < j3 and if i3=j3 then i4 < j4.

If no solution exists then return an ArrayList containing only -1.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains a single integer N denoting the size of the array.

The second line of each test case contains N space-separated integers denoting the array elements at various indices.
Output format :
For each test case, return an array list representing the indices that satisfy the given condition.
Note:
You don’t have to print anything; it has already been taken care of. Just implement the given function. 
Constraints:
1 <= T <= 100
1 <= N<= 100
1 ≤ ARR[I] ≤ 10^7

Time Limit: 1 sec
Approach 1

 The idea is to keep track of all possible cases for each index and for this we will have to use four nested loops checking for each case that gives us X + Y = Z + W.

 

  • Declare the ANS arraylist store answers and run four nested loops I, J, K, L each running from index 0 to N-1.
  • In the last loop check for the condition i.e. IF(ARR[I]+ARR[J])==(ARR[K]+ARR[L]) && I<J && K<L && I<K && J!=K && J!=L).
  • Now after the loops check if the arraylist ANS is empty then add -1 to it and return.
  • Else return arraylist ANS.
Try Problem