According to the editorial,
sum of all lengths of distinct element subarrays in this subarray is ((j-i) * (j-i+1))/2 .
How? the possible lengths of subarrays are 1, 2, 3,……, j – i +1. So, the sum will be ((j – i ) * (j – i +1))/2.
But the lengths can repeat right? in the given sample input we have 3 subarrays of length 1.So how can you apply the formula of sum of n natural numbers there??
You are thinking is natural but here’s where you get wrong.
Consider this example.
1 2 3 1
In first go, you get 1 2 3 in your bag. And we apply formula.
In next go, You get 2 3 1 in your bag then we again apply formula.
If you go by your formula/method, you will end up adding (2,3) , (2) , (3) twice. Right? Think!
Wait. Let me clear what i understood problem actually is…
We are given 123, so possible subsets are 1,2,3,12,23,123 right? and summing the lengths we get 1+1+1+2+2+3=10
Here, the entire array is unique so according to the formula, ((2-0*(2-0+1))/2=3. Can you elaborate the case of 1231…?