how sir inserted element in the video in unordered_map
m.insert(a[j]) isn’t valid as a pair is to be added
moreover while finding the max j
when loop terminates j that we will get will 1 greater than correct value
sir didn’t managed that
plzz explain me the correct approach to the
question sir
Hello @yatin,
The approach is correct with two logical mistakes as you have pointed:
Yes, there is a mistake in the choice of data structure.
Use unordered_set s; instead of map.
You can use the following expression:
ans += ((j - i) * (j - i + 1))/2;
I have conveyed this to your mentor.
Hope, this would help.
Give a like if you are satisfied.
can you plz explain how this formula will work fine and the earlier one will fail
Sure @yatin,
As you have yourself pointed that when loop terminates j that we will get will 1 greater than correct value
So to neutralise that extra 1 in j, I have just subtracted 1 from both the brackets.
Mathematical Explanation:
The formula used in the video:
ans += ((j - i+1) * (j - i + 2))/2;
Actually j=j’-1,
Where
j: is the actual value of j required by the formula.
j’: is the incremented value that we are getting
Substituting j in the above formula:
ans += (((j’-1) - i+1) * ((j’-1) - i + 2))/2
ans += ((j’ - i) * (j’ - i + 1))/2;
Hence Proved.
Hope, it is clear now.
Give a like if you are not satisfied.
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.