Nice Problem | Find the number of pairs in sorted array whose sum is x

Question

Follow up : Find the number of pairs in array whose sum>=x

Follow up : Find the number of pairs in array whose sum<=x

Expectation :

O(n) time and O(n) space ..

Followup : O(n) time and O(1) space .

Rules :

1)Explanation of algorithm in your answer is a must .

2)Writing code is optional .

3)If code is written , make sure to you use format option from the editor .

Answer 1

Normal 2 Pointer approach

 

int solve(vector<int> &arr,int x){

int l=0,r=arr.size()-1;

int ans=0;

while(l<r){

if(arr[l]+arr[r]>=x){

ans+= (r-l);

r--;

}

else{

l++;

}

}

return ans;

 

}

Comments

Why ans+=(r-l)