0 like 0 dislike
1,882 views
| 1,882 views

0 like 0 dislike

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.

by Expert (111,270 points)
0 like 0 dislike

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?

by Expert (111,270 points)