AJAY-GOJO's blog

Infosys Sp OA problem -- 2024
By AJAY-GOJO, history, 3 hours ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
61 minute(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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) / 2

Now, the equation boils down to => X[i] <= -Y[j] => X[i] + Y[j] <= 0

This 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<int, int>
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.

→ Reply