### PROBLEM LINK:

### DIFFICULTY:

EASY.

### PREREQUISITES:

Hashing

### PROBLEM:

Given an array, find out pair of numbers such their sum modulo **M** is less than or equal to **X**.

### QUICK EXPLANATION:

As the naive solution will have time complexity of **O(n ^{2})** which will not pass, So we can make a count array A, where A[p] = count of numbers whose value modulo

**M**is

**p**and we can check if first number module

**M**is

**p**, then in how many ways we can select another number. The time complexity of above solution will be

**O(M+N)**.

### EXPLANATION:

Array **A** contains economy rates of the bowlers.

The naive solution will look like:

```
long long int answer = 0;
for(int i =0 ; i < N ; i++)
for(int j = 0 ; i< N ; j++)
if( (A[i] + A[j] <= x)
answer++;
cout<<answer<<endl;
```

But the given solution has time complexity O(n^{2}) which will not pass in the given time limit.

As you can notice that, the value of **M** is not large and a solution having time complexity of **O(M)** will pass.

** An O(M^{2}) approach: **

Make an array **B**. where

B[k] = count of numbers in array **A** which has value of **k** on taking modulo **M**.

Now another naive approach can be written in following manenr having time-complexity of **O(M ^{2})**.

```
long long int answer = 0;
for(int i = 0 ; i< M ; i++)
for(int j = 0 ; j< M ; j++)
if( (i+j)%M <= x)
answer += B[i]*B[j];
cout<<answer<<endl;
```

In this approach, we are taking all such number, whole modulo **M** value **i** or **j** and if their sum modulo **M** is less than or equal to **x**, then they will contribute to the answer.

The above solution will also not pass, as time complexity of given solution is **O(M ^{2})**.

Now we will try to optimize the solution to **O(M)**.

as we can observe that if we want **((i+j)%M) <=x**, and we have fix the value of i. then j can take only few contiguous values.

There will be two cases.

So, for the case I where i<=x:

```
for(int i=0 ; i<= x; i++)
answer += B[i]*(B[0] + B[1] + ....+ B[x-i])
```

As we can see that the values which we are multiplying will B[i], their indices are contiguous in nature, so we can use the idea of prefix sum to get the value of the range sum in O(1) time.

Define Pre[i] = B[0] + B[1] + … + B[i]

then B[i] + … + B[x-i] = Pre[x-i] - Pre[i-1]

So modified code will look like :

```
for(int i=0 ; i<= x; i++)
answer += B[i]*(Pre[x-i] - Pre[i-1]);
```

Similarly we can handle the second case when ** i>=x ** . Time complexity of the above solution will be **O(M+N)**, which will easily pass in given time limit.

### Editorialist’s Solution:

Editorialist’s solution can be found here.