Question

DE Shaw internship round | Set-25 | 2022

Answer 1

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 ?

 

 

 

Answer 2

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;