Subarray sum with distinct elements

#1

how did u derive the formula (j-i+1)*(j-i+2)/2
pls explain it clearly

#2

@i_am_dekard_shaw
hello Abdullah,
let say from index i to index j all elements are distinct.

Now number of element in this subarray will be-> j-i+1 (say n)

if we pick any two indices from this subarray then that will also contain all distinct element.

so number of ways to pick two indices will be . nc2 + n ( n is when we pick all subarray of length 1)

now nc2= (n) * (n-1)/2
nc2+n=n * (n-1)/2 +n => n*(n+1)/2
now substitute value of n .
n*(n+1)/2=> (j-i+1) * (j-i+1 +1) / 2 = (j-i+1) * (j-i +2 ) /2

1 Like
#3

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.