Inversion count

#1

Sir , in inversion count question , Can “Ai” (which is value at ith position of array ) be greater than N (No. of elements)??

#2

@vg5823967
Yes. It is possible. Infact , the value can be -ve as well. Hence we need to perform coordinate compression before using BIT for this problem or else we are likely to get a runtime error or a wrong solution.

#3

what if we take size of BIT array equal to the max. of [Ai]

#4

@vg5823967
Given the constraints , you won’t be able to create such a large array. Even if you could, you still won’t be able to handle the negative numbers.

#5

It also handles duplicate numbers ??

#6

@vg5823967
Consider this array
2 35 -1 2 50

After coordinate compression , it becomes
2 3 1 2 4

I hope this answers your query about duplicate numbers.

#7

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.