Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 22 Dec, 2020

Moderate

```
1. All four numbers should exist at different indices in the given array.
2. The answer is case-sensitive.
```

```
The first line of the input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains two space-separated integers ‘N’ and ‘TARGET’ denoting the number of the elements present in the sequence and the target sum respectively.
The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array 'ARR'.
```

```
The only line of output of each test case should contain “Yes” (without quotes) if there exist 4 numbers (having different indices) that give sum ‘TARGET’ else “No” (without quotes).
```

```
You don't need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10^2
4 <= N <= 2*10^2
-10^9 <= ARR[i] <= 10^9
-10^9 <= TARGET<= 10^9
Time Limit: 1 sec
```

```
Can you try solving the problem with less than O(N^2 * log(N)) time complexity?
```

- We will check the sum of every possible combination of four indices using 4 nested loops.
- If the sum is equal to the ‘target’ that means we found our quadruple. So, we return true in this case else we simply return false.

- We first need to sort the array and fix the two indices ‘i’ and ‘j’ for our first element and second element respectively, where 0 <= i < N-3 , i+1 <= j < N-2.
- The idea here is: For all pairs of the first and second element, we find the possible indices for the third and fourth element in a single loop using two pointer technique.
- Let us understand how two-pointers will help us, we put two-pointers at the starting and the ending of the remaining suffix [j+1, N-1]. Suppose left = j+1, and right = N-1 so our current sum will be arr[i] + arr[j] + arr[left] + arr[right] now if this sum is equal to ‘target’ that means we found one correct quadruple so we return true in that case.
- If the sum is less than ‘target’ that means we need to increase our sum so make it equal to the required sum ‘target’. You can observe that arr[i] + arr[j] is constant and we can only change arr[left] or arr[right].
- As we already sort the array this implies arr[left] < = arr[right] and arr[right] is already having a greater value so we can’t increase arr[right] further. In this case, we move forward through the ‘left’ pointer because arr[left+1] >= arr[left] to match up with the required sum.
- Else if the sum is greater than ‘target’ that means we need to decrease our current sum so in this case, we move backward through the ‘right’ pointer because arr[right-1] <= arr[right] to match up with the required sum.

- At last, if we can not find any valid quadruple then we return false in that case.

- We will create a temporary array temp[] to store the sum of all possible pairs.
- Now we sort this temp[] array. As each element of temp[] contains the sum of two elements so the problem reduces to finding the two pairs in the temp[] such that their sum is equal to ‘target’.
- We can use two pointer technique to check whether there exist two pairs in the temp[] array that gives the sum = ‘target’. Similar to the above approach we will put the first pointer (left) at the starting and the second pointer (right) at end of temp[] array.

Now if temp[left] + temp[right] = target that means we found a pair but we also need to check whether these two elements of temp have an element of arr[] in common or not for ensuring that the elements we pick have distinct indexes.

- To check the distinct indexes we need to declare the type of temp as a structure in which we can store sum and both indexes as separate fields.
- We just access both indexes of temp[left] and temp[right] and if they have any common index then this can not be a valid pair.
- If temp[left] + temp[right] < target so similar to the above approach we will move our ‘left’ pointer to right else we move the ‘right’ pointer to the left.

- We will store the sum of all possible pairs in a hashmap having sum as its key and a pair of indexes as its value.
- To find pair sum we run 2 nested loops for choosing the first and the second element of quadruple let us say their sum is arr[i] + arr[j] then we try to find the remaining sum ( target - arr[i] - arr[j] ) from the hashmap.
- If the hashmap contains a key = target - arr[i] - arr[j] that means we have a pair present in the hashmap such that their sum is ‘target’.
- In the next step similar to the above approach we must check whether these two pairs of elements have an element of arr[] in common or not for ensuring that the element is not considered more than once.
- For doing so we simply extract the indexes of other pairs ( target - arr[i] - arr[j] ) from the hashmap and check if the two indexes are different from ‘i’ and ‘j’ or not.