### AJAY-GOJO's blog

By AJAY-GOJO, history, 5 weeks ago,

frequency problem

you have two function defined as follows: --> frequency (left,right,val) : return the number of element in the range [left,right] that are equal to value --> distinct (left,right): return the number of distinct element in range[left,right]

find the number of pair(i,j) the satisfy the following conditions: freuqncy(1,i,A[i]) + freuency(j,N,A[J]) <= L distinct(1,i)/2 L + L distinct(j,N)/2 L . since answer can be very large return it modulo 10^9+7.

note L X L represent the greatest integer less than or equal to x . 1<=i<j<= N

can anyone give me apporach of this mine give TLE.

test case 1 N = 5 A = 2,2,3,1,5

test case 2 N= 5 A = 5,5,5,5,5

• -1

 » 5 weeks ago, # | ← Rev. 2 →   0 Generally while solving questions related to pairs satisfying an equation, re-writing the equation by separating out same variables on same side of equality helps.Let's denote frequency as f and distinct as d.=> f(1, i, A[i]) + f(j, N, A[j]) <= d(1, i) / 2 + d(j, N) / 2=> f(1, i, A[i]) — d(1, i) / 2 <= — ( f(j, N, A[j]) — d(j, N) / 2 )Let's denote an array X, where X[i] represents f(1, i, A[i]) — d(1, i) / 2 and an array an array Y, where Y[j] represents f(j, N, A[j]) — d(j, N) / 2Now, the equation boils down to => X[i] <= -Y[j] => X[i] + Y[j] <= 0This becomes a problem where you have been given two arrays, where you need to find the pairs whose sum is less than or equal to zero.Now the question is how do you calculate array X and array Y, This can be done using map. mp = map for i in (1, n): mp[A[i]] += 1 f = mp[A[i]] // the frequency of A[i] in 1 to i d = mp.size() // mp.size() is the number of distinct elements from 1 to i X[i] = f - d / 2 Similarly, Y can also be calculated looping from the end.
•  » » 5 weeks ago, # ^ |   0 Thankyou so much. it really helpful for me