Find Four Elements That Sums To A Given Value | Four Sum

 

Find Four Elements That Sums To A Given Value

fgdf

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

Sample Input 1:

2
5 9
1 3 3 10 2
6 20
2 4 6 3 1 1

Sample Output 1:

Yes
No

Explanation For Sample Input 1:

Test case 1:
The elements at indices (0, 1, 2, 4) gives sum 9 i.e, ARR[0] + ARR[1] + ARR[2] + ARR[4] = 9. Hence the answer is Yes.

Test case 2:
None of the combinations of 4 numbers gives 20 as 'TARGET'. Hence the answer is No.  

Sample Input 2:

2
5 15
0 10 1 2 2
6 20
-2 12 -1 1 20 1 

Sample Output 2:

Yes
Yes

The solution to the Above Question is -

#include<bits/stdc++.h>

string fourSum(vector<int> arr, int target, int n) {

    // Write your code here.

    unordered_map<int,pair<int,int>> m;

    for(int i=0;i<arr.size();i++)

    {

        for(int j=i+1;j<n;j++)

        {

            m[arr[i]+arr[j]]=make_pair(i,j);

        }

    }

    

    for(int i=0;i<arr.size();i++)

    {

        for(int j=i+1;j<n;j++)

        {

            int x=arr[i]+arr[j];

            

            if(m.find(target-x)!=m.end())

            {

                pair<int,int> p=m[target-x];

                

                if(i!=p.first && i!=p.second && j!=p.first && j!=p.second)

                    return "Yes";

            }

        }

    }

    return "No";

}

Thank you for reading this.