Question

Goldman Sachs || OA || Noble Element || 2022 || Set-41

Answer 1

C++ Code:
Also, in this question, a,b,c can be equal as well.

 

int nobleElements(vector<int>&nums){
    int n=nums.size();
    int res=0;
    //nums[a]+nums[b]+nums[c]==nums[d], where a<=b<=c<d
    //nums[a]+nums[b]==nums[d]-nums[c];
    map<int,int>mp;
    mp[nums[n-1]-nums[n-2]]++; //nums[d]-nums[c]
    for(int b=n-2;b>=0;b--){
        for(int a=b;a>=0;a--){
            res += mp[nums[a]+nums[b]];
        }
        for(int k=b+1;k<n;k++){
            mp[nums[k]-nums[b]]++;
        }
    }
    return res;
}

 

Thanks for the idea.

This question is same as the question which was asked in leetcode's weekly contest.
https://leetcode.com/problems/count-special-quadruplets/

Answer 2

An array of N integers is given.
The ith element is called noble , if it can be expressed as the sum of three elements from the array having indices smaller than i. An element can be used more than once in the sum expression.
Find total number of noble elements in the array.

 

Constraints:
1 <= N <=10000
-100,000 <= value of array elements <= 100,000

 

Can someone provide an optimal solution to this question?