why are we finding total number of unique elements (i.e. sum of unique elements in sub array).
Total unique elements
Hey @himanshugupta8
This may help :
For each index i we will find the number of pairs ( l , r ) (before swapping) such that i is the first occurence of a(i) in the chosen segment. Let f ( i ) be previous occurence of a(i) before i (if i is the first occurence, then f ( i ) = 0 if we suppose the array to be 1-indexed). Let’s find the number of pairs such that l ≤ r , and then multiply it by 2 and subtract 1 for this index. l has to be in segment ( f ( i ), i ], and r has to be in segment [ i , n ], so the number of ways to choose this pair is ( i - f ( i ))( n - i + 1).
The value we receive as the sum of these values over all segments is the total number of distinct elements over all pairs ( l , r ), so we need to divide it by the number of these pairs.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.