We can use following logic : -
1- create a copy of original array A - O(n)
2- sort the original array using randomised quick sort - O(n log n)
3 - iterate in copy array B from left and for every element in B
find its position in A using binary search
distance = position of B[i] in A) -
@all i have posted the solution of same problem few times back ,
search in group thread
i used BST & using that inversion count can be calculated in O(nlogn)
if you found any error on that then let me know
Thanks
Shashank
CSE,BIT Mesra
--
You received this message because you are subscribed to