Thread: find pair of numbers

Give an unsorted array find count of pairs of numbers[a,b] where a > b and b comes after a in the array.
Eg. {8,3,6,10,5}
the count of such numbers is 5. i.e. (8,3), (8,6), (8,5), (6,5) and (10,5)

Use Binary search tree.



Keep a global counter and keep an internal node counter which keeps the count of the right subtree.
When you move right, increment the internal counter of the current node you are checking against, when you move left increment the global counter by one AND by the number in the internal counter.
So in the example, insert 8, GC=0, insert 9, GC=0, internal counter of 8=1, insert 10, GC=0 internal counter of 8=2, and internal counter of 9=1.
now when you insert 7, increment global counter by one and add 2 to it since 8's internal counter is 2, that means there are 2 more numbers greater than 7.
So we get 3 as the answer.

1) consturct binary tree, maintain a counter
2) while inserting into a binary, keep count of all element inserted right side of a node
3) when node is insert left side of node, counter=counter+1+numberOfRightNode( step 2 we are keeping count of right element for each node)
4) if node is inserted right side, just increment rightCounter of that node
5) Ans is counter when all element is inserted

Simply count the number of consecutive swaps required to sort the unsorted array. The pair of numbers which are sorted would be the solution.