Cost of an array A, here, is the number of pairs i and j (i < j), such that Ai > Aj. Determine the cost of the given array A of N elements.

help
, ,
1

Please Explain your approach except brute force due to high constraints.

2

You can use Balanced BST here Where each node is storing value and number of it’s children…

Start from 0 in array and iterate… then you just have to find out number of elements greater than Ai in existing Balanced BST. After that just add node and update tree till root…

Hope it’s clear enough… Here Complexity would be O(nLog(n)) n is number of elements in array.

3

But the array may not be sorted. And if the array is not sorted, then the condition that i<j will not hold. For example, if the array is 3 1 5 1 2 3 4 2, then (5,1) is a valid pair but (1,5) is not. How do you plan to use balance BST here ?

4

I am putting node in Balanced BST one by one while traversing array, That will take in account what you are saying… as for left 1, 5 is not yet added in BST so It will not be counted… But for right 1, 5 has been added so this pair would come in count…

5

This is known as “Inversion Counting” problem.

It can be solved using a Binary Indexed Tree (BIT) or Merge Sort.

The following links explain both the approaches.

Using BIT: http://www.geeksforgeeks.org/count-inversions-array-set-3-using-bit/

Using Merge Sort: http://www.geeksforgeeks.org/counting-inversions/

2 Likes
6

Thats clean… :slight_smile:

1 Like
7

Got it. Thanks. Any good references to learn and practice Balanced BSTs?

8

This should help… http://www.geeksforgeeks.org/avl-tree-set-1-insertion/