0 like 0 dislike
967 views
| 967 views

## 2 Answers

0 like 0 dislike
Best answer

Discuss the approach that you will try, i don't understand their constraints, we can solve it in n^2 why they are providing constraints of n^3 ?

by Expert (111,350 points)
0 like 0 dislike
The optimal solution runs in O(n) time, using an unordered_map, it is a variant of the classic two sum problem.

int getMaximumScore(vector<int> balls,int k){

int ans=0;
unordered_map<int,int> mymap;

for(int x:balls){
int target=k-x;

if(mymap[target]>0){
mymap[target]--;
ans++;
}
else mymap[x]++;
}
return ans;
}

int main(void){

cout<<getMaximumScore({4,2,1,3},5)<<endl;
cout<<getMaximumScore({2,1,3},6)<<endl;
cout<<getMaximumScore({1},1)<<endl;

return 0;
}
// output: 2 0 0

I guess the constraints were 10^5, 10^9 respectively
Time complexity: O(n*log(n))
And this can be solved using 2 pointer technique and sorting the identification numbers of balls

int n = balls.size();
sort(balls.begin(),balls.end());

int l = 0, r = n-1, cnt = 0;
while (l < r){
if(balls[l] + balls[r] == k){
cnt++;
l++;
r--;
}else if(balls[l]+ balls[r] < k){
l++;
}else{
r--;
}
}

return cnt;
by Expert (111,350 points)