Equal Pairs

Easy

0/40

Average time to solve is 10m

Contributed by

3 upvotes

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

3
6
3 4 2 8 1 2
4
1 4 3 2
5
1 8 2 9 19

Sample Output 1 :

0 2 1 4 
0 1 2 3
0 3 1 2

Explanation For Sample Input 1:

For the first test case:
The given array is {3,4,2,8,1,2} we can see that 3 + 2 = 4 + 1 which are at indices 0,2,1 and 4 .

For the second test case:
The given array is {1,4,3,2} we can see that 1 + 4 = 3 + 2 which are at indices 0,1,2 and 3 .

For the third test case
The given array is {1,8,2,9,7} we can see that 1 + 9 = 8 + 2 which are at indices 0,3,1 and 2 .

Sample Input 2 :

3
4
4 5 6 99
7
1 7 3 4 5 6 2
8
1 19 3 17 4 5 2 18

Sample Output 2 :

-1
0 1 2 4  
0 1 2 3

Hint 1

Hint 2

Try to consider all possible combinations of the numbers.

Approaches (2)

Approach 1

Approach 2

Brute Force

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.

Time Complexity

O(N ^ 4), Where ‘N’ denotes the number of elements in the Array.

because we are using four nested loops.

Space Complexity

O(1)

We are using constant space.

(100% EXP penalty)

Equal Pairs

Console