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 &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
int main(){
    std::vector&lt;long long&gt; tstCases;
    std::vector&lt;long long&gt; okset;
    std::vector&lt;long long&gt; testset;
    for(int i =0;i&lt;2;i++){
        long long cases;
        std::cin &gt;&gt; cases;
        tstCases.push_back(cases);
    }
    long long n = tstCases.at(0);
    long long k = tstCases.at(1);
    for(long long i =0;i&lt;n;i++){
        long long cases;
        std::cin &gt;&gt; cases;
        if(cases&lt;=k){
            if(cases &lt; k/2){
                okset.push_back(cases);
            }else{
                testset.push_back(cases);
            }
        }
    }
    long long l = okset.size();
    long long p1 = (l*(l-1))/2;
    long long p2 = 0;
    sort(testset.begin(),testset.end());
    for(long long itr1 : okset){
        for(long long itr2 : testset){
            if(itr1+itr2 &gt;= k){
                break;
            }else{
                p2++;
            }
        }
    }
    long long p = p1+p2;
    std::cout &lt;&lt; p &lt;&lt; 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] &lt; k.  When this happens, add j-i to the solution count, and increment i.  Do not reset j.
Stop when i &gt;= 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 &lt; j; i++) {
    while (j &gt; i &amp;&amp; a[i]+a[j] &gt;= k)
        j--;
    count += j - i;
}