Yup, it is O(n log n).

You only need to print the last four digits of the answer i.e mod 10000.

I guess 15.

No, I wasted 1/2 of the time trying to get 100 on the second one after I had got 75.

I made one case like that manually and my code worked fine on that.So,I pretty sure my code works fine for those cases

I also did the same but got 75.

#include <bits stdc++.h="">
using namespace std;
 
int main() {
     long long int n,k;
     cin >> n >> k;
     long long int a[n];
     for(int i = 0;i < n;i++)cin >> a[i];
     sort(a,a+n);
     long long int i = 0,j = n-1,ans = 0;
     while(i < j){
         if(a[i] + a[j] < k){
             ans += j-i;
             i++;
         }
         else j--;
     }
     cout << ans;
     
	return 0;
}

Nope, It wont give TLE. Also, I recommend you to read this Binary Search – topcoder .

Your code will fail on test cases like : 5 4 1 2 3 4 5.

The answer is 1 but your code will output 0.

You need to add an extra loop or binary search for each position i to find a position j such that a[i] - a[j] >= k and then add j+1 to the counter.

Here's the official solution -

In this problem, the necklace size is small enough (350) that we might as well just try breaking the necklace at each point and see how many beads can be collected. This will take approximately O(n^2) time, but n is small enough that it won't matter.The code is slightly simple-minded in that we might count the same beads twice if they can be taken off either side of the break. This can only happen if all beads can be taken off the necklace, so we just check for that at the end.

#include <stdio.h>
#include <string.h>
#include <assert.h>
#define MAXN 400
char necklace[MAXN];
int len;
/* 
 * Return n mod m.  The C % operator is not enough because
 * its behavior is undefined on negative numbers.