Counting pairs of integers whose sum is less than a given threshold

Recently I was going through this codechef problem while practicing for the upcoming zoc.

The problem asks to calculate number of combinations of the given numbers where the sum is less than another given number.

Previously I had a bruteforce algorithm which gave the correct answer but took a lot of time, in some cases even more than a second which raised a TLE error in codechef.

I changed my whole algorithm to get rid of that TLE error and also almost got that but for the last test it still gets stuck.

#include 
#include 
#include 
int main(){
    std::vector tstCases;
    std::vector okset;
    std::vector testset;
    for(int i =0;i> cases;
        tstCases.push_back(cases);
    }
    long long n = tstCases.at(0);
    long long k = tstCases.at(1);
    for(long long i =0;i> cases;
        if(cases= k){
                break;
            }else{
                p2++;
            }
        }
    }
    long long p = p1+p2;
    std::cout << p << std::endl;
    return 0;
}

Note : I am using long long because the problem instructed me to do so and I am lazy enough to do it by myself so I used replace all. Sorry for that.

A better algorithm

Your current algorithm has a worst case time of \$O(n^2)\$, when the list is half filled with zeroes, and half filled with k/2. You can solve the problem in \$O(n \log n)\$ time by doing the following:

• Sort the input.

• Use two indices, one starting at the low end and one starting at the high end. Call these indices i and j.

• For each i, walk j down until a[i] + a[j]






• Stop when i >= j`.

Steps 2-4 solve the problem in \$O(n)\$ time, but the sort in step 1 takes \$O(n \log n)\$ time. Here is a code snippet to illustrate the key part:

for (int i=0, j=len-1; i  i && a[i]+a[j] >= k)
        j--;
    count += j - i;
}

StackExchange Code Review Q#139506, answer score: 9