Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 22 Dec, 2020

Find Four Elements That Sums To A Given Value

Moderate
Asked in companies
AmazonGoogleOYO

Problem statement

You are given an array/list 'ARR' of ‘N’ integers and an integer value ‘TARGET’. You need to check whether there exist four numbers (ARR[i], ARR[j], ARR[k], ARR[l]) such that (0 <= i < j < k < l < N) and ARR[i] + ARR[j] + ARR[k] + ARR[l] = 'TARGET'.

Note:
1. All four numbers should exist at different indices in the given array.
2. The answer is case-sensitive.
Input Format:
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'.
Output Format:
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).
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10^2
4 <= N <= 2*10^2   
-10^9 <= ARR[i] <= 10^9
-10^9 <= TARGET<= 10^9 

Time Limit: 1 sec

Follow Up:

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

Approaches

01 Approach

  1. We will check the sum of every possible combination of four indices using 4 nested loops.
  2. 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.