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.
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 timecomplexity of O(M^{2}).
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:
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[xi] = Pre[xi]  Pre[i1] So modified code will look like :
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. asked 14 Jan '15, 23:05

There's bugs in both the recurrences.
answered 07 Oct '15, 02:37

Having understood the first and the second approach, I am confused and unable to understand the O(M) approach fully.
Why is T being calculated up to M+X and when a[i]<=X why is T[M+Xa[i]]  T[M1a[i]] also being added to the ans? Could you kindly explain the approach/cases in a little more detail? Thanks. Regards, Ankit. answered 16 Jan '15, 12:22

Theres typo in editorial In case 1: it shud be 0<=j<=xi answered 03 Dec '15, 17:52

@amitpandeykgp Please fix the solution link it's redirecting me to the same page.
Thanks :)
Added, thanks.