You are not logged in. Please login at to post your questions!



Problem Links


BIT,Merge Sort

Problem Statement
Given an array of n distinct integers we have to find the minimum number of swaps in order to make it similar to the another array.

Explanation Let A[] be an array which is to be converted to the array B[]. Let us make another array C which stores the index of a given element A[i] in array B.
For example
Let array A[]=[23, 34, 56, 78]
and array B[]=[34,56,78,23]
then array C will be

[4 ,1 ,2 ,3 ]
(index starts from 1)

Now the problem only reduces to finding the minimum number of swaps in array C in order to make it a sorted array. This further reduces to finding the number of inversions which we can easily find by using BIT (Binary Index Tree).

Here’s a very nice article about finding the number of inversions .

Another way of finding inversions is by using merge sort. Here’s an interesting quora article about finding the number of inversions using merge sort.

Editorialist’s solution

This question is marked "community wiki".

asked 01 Feb '15, 01:07

murdocc007's gravatar image

accept rate: 12%

edited 01 Feb '15, 14:56

While reading about how to solve it on the web, I came across two terms "Cayley distance" and "Kendall Tau distance". Is the problem related to either one of them?


answered 01 Feb '15, 16:12

dragonemperor's gravatar image

accept rate: 10%

This problem is based on "Kendall Tau Distance"

(01 Feb '15, 19:55) pulkitsinghal6★

If I am not wrong, the worst case complexity of the above solution is of the order O(N^2). Can someone tell me how it got accepted in just 0.04 seconds?


answered 01 Feb '15, 16:20

sandy999's gravatar image

accept rate: 10%

edited 04 Feb '15, 16:29

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 01 Feb '15, 01:07

question was seen: 2,455 times

last updated: 04 Feb '15, 16:29