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(n2) 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(n2) 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(M2) 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(M2).
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(M2).
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.
