Last Updated: 12 Jan, 2021
Equal Pairs
Easy
Asked in company
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
Approaches
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.
In this approach, we will store the value sum and indices that lead to that sum in a hashmap i.e. we will declare a hashmap of Integer, ArrayList in which key will be the sum and ArrayList will store the indices to that sum. further, we will check for the sum and if it existed in the hashmap then we check for that whether the answer is valid or not and update it finally.
Now let’s discuss the algorithm-
- Declare the hashmap<Integer, ArrayList<Integer>> MAP and initialize the ANSWER ArrayList;
- Iterate the array by running a loop from index I=0 till the end of the array
- And inside this loop run one more from index J=0 till the end of the array.
- Now get the sum for the current iteration i.e. ARR[I]+ARR[J].
- Now check whether this sum exists in the hashmap or not and if it exists then just then check whether the indices are valid or not by applying the conditions of the indices.
- If the indices are valid then just add it to the MAP as arraylist else go for the next iteration.
- Else if the sum does not exist in the MAP then just put the sum and value of indices in the map.
- After both loops end check whether the answer you obtained is correct or valid by again running two-loop from index I=0 and J = I+1 repeat step number four except for checking indices you will check for the validity of whether the obtained answer is correct or not.
- If the list is empty till the end then just add -1 to it and return.