I was going through some sample questions on the net. I found a question where you have to count the number of pairs that can be formed according to the info given below:

Hobbes has challenged Calvin to

display his chewing skills and chew

two different types of Chewing

Magazine’s Diabolic Jawlockers chewing

gum at the same time. Being a generous

sort of tiger, Hobbes allows Calvin to

pick the two types of gum he will

chew.Each type of chewing gum has a

hardness quotient, given by a

non-negative integer. If Calvin chews

two pieces of gum at the same time,

the total hardness quotient is the sum

of the individual hardness quotients

of the two pieces of gum.Calvin knows that he cannot chew any

gum combination whose hardness

quotient is K or more. He is given a

list with the hardness quotient of

each type of gum in the Diabolic

Jawlockers collection. How many

different pairs of chewing gum can

Calvin choose from so that the total

hardness quotient remains strictly

below his hardness limit K?For instance, suppose there are 7

types of chewing gum as follows:

Chewing gum type 1 2 3 4 5 6 7

Hardness quotient 10 1 3 1 5 5

0If Calvin’s hardness limit is 4, there

are 4 possible pairs he can choose:

type 2 and 7 (1+0 < 4), type 3 and 7

(3+0 < 4), type 2 and 4 (1+1 < 4) and

type 4 and 7 (1+0 < 4).Input format

Line 1 : Two space separated integers

N and K, where N is the number of

different types of chewing gum and K

is Calvin’s hardness limit.Line 2: N space separated non-negative

integers, which are the hardness

quotients of each of the N types of

chewing gum.Output format

The output consists of a single

non-negative integer, the number of

pairs of chewing gum with total

hardness quotient strictly less than

K.Sample Input

7 4 10 1 3 1 5 5 0

Sample Output

4

Test data

In all subtasks, you may assume that

all the hardness quotients as well as

the hardness limit K are between 0 and

1,000,000, inclusive.Subtask 1 : 2 ? N ? 2,000.

Subtask 2 : 2 ? N ? 100,000.

Live evaluation data

Subtask 1: Testcases 0,1,2,3.

Subtask 2: Testcases 4,5,6.

Limits

Time limit : 3s

Memory limit: 64 MB

I used a code which has 2 for loops going through to make a pair. But it is very inefficient since the time would be N*N times which would be too much if N goes upto 100,000. SO I was wondering if there’s any other method? Here is my code:

#include “iostream” using namespace std; int main() {

unsigned long int N,i,j;

int K, *arr,cnt=0;

cin>>N;

cin>>K;

arr = new int [N];`for(i=0;i<N;i++) { cin>>arr[i]; } for(i=0;i<N;i++) { if(arr[i]>=K) { continue; } for(j=i+1;j<N;j++) { if((arr[i]+arr[j])<K) { cnt++; } } } cout<<cnt; return 0; }`

I would appreciate any help. Thanks.