Virus - 9 months ago 48

C++ Question

This Is The Question

Here is my solution:

`#include <iostream>`

using namespace std;

int main(){

unsigned long numberOfGums;

unsigned long hardnessLimit;

unsigned long counter = 0;

cin >> numberOfGums;

cin >> hardnessLimit;

unsigned long gums[numberOfGums];

for(unsigned long i=0; i<numberOfGums; i++){

cin >> gums[i];

}

for(unsigned long i=0; i<numberOfGums; i++){

if(gums[i] < hardnessLimit){

for(unsigned long j=i+1; j<numberOfGums; j++){

if((gums[i] + gums[j]) < hardnessLimit){

counter++;

}

}

}

}

cout << counter << endl;

return 0;

}

This program is giving me

I have tried stuff like using

What can i do to improve this program, or what is a better approach to this problem.

I tried this also, but got the same error:

`#include <iostream>`

using namespace std;

int main(){

long numberOfGums;

long hardnessLimit;

long counter = 0;

long temp = 0;

cin >> numberOfGums;

cin >> hardnessLimit;

long gums[numberOfGums];

for(long i=0; i<numberOfGums; i++){

cin >> temp;

if(temp < hardnessLimit){

gums[i] = temp;

}

}

for(long i=0; i<numberOfGums; i++){

if(gums[i] != -1){

for(long j=i+1; (j<numberOfGums); j++){

if(((gums[i] + gums[j]) < hardnessLimit) && gums[j] != -1){

counter++;

}

}

}

}

cout << counter << endl;

return 0;

}

Answer Source

Your solution is `O(N^2)`

which will definitely time out given the constraints.

A more efficient solution is an `O(NlogN)`

solution. This is the basic outline of the algorithm:

Sort the array. This takes

`O(NlogN)`

time.Now for each element in the sorted array, say

`p`

, search for an element index(right of the element`p`

) in the array such that the value at that index is less than`k - p`

. Use binary search for this. After finding this index, you can easily calculate the number of such pairs associated with the element`p`

. This complete step takes`O(logN)`

time for each elementDo the above process for all elements in the array except for the last element as there is no array left to its right.

You will get the answer by summing up all the pairs for each element `p`

that you have obtained

Hope it helps!!!

**Edit:** I am adding the C++ implementation of the above algorithm. This solution passes all the test cases on CodeChef.

```
#include <iostream>
#include <algorithm>
using namespace std;
int binsearch(int a[],int n, int x)
{
int low, high, mid, k=-1;
low = 0;
high = n-1;
while(low<=high)
{
mid = (low+high)/2;
if(a[mid] <= x-1){
k = mid;
low = mid+1;
}
else{
high = mid-1;
}
}
return k;
}
int main()
{
int n, k, i, j;
long long ans = 0;
cin>>n>>k;
int arr[n];
for(i=0;i<n;i++)
{
cin>>arr[i];
}
sort(arr,arr+n);
j = 0;
while(j<n-1)
{
if(k-arr[j] > 0)
{
int ind = binsearch(arr,n,k-arr[j]);
ans = ans + (ind-j>=0 ? (ind-j):0);
}
j++;
}
cout<<ans<<endl;
return 0;
}
```