#1  
Old 11-22-2016, 12:44 AM
CodeGroundOnlineTests CodeGroundOnlineTests is offline
Junior Member
 
Join Date: Nov 2016
Posts: 8
Default Count Inversions

What is an inversion?
Let A be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.
For example, the array {2,3,8,6,1} has 5 inversions: (2,1) (3,1) (8,6) (8,1) and (6,1)
Trivial Solution to count the number of inversions in an array
countInversions = 0;
for i = 1 to N
** for j = i+1 to N
****** if(A[i] > A[j])
*********** countInversions++;

The overall time complexity for this approach is*O(n^2)
Using Merge Sort to count the number of inversions in O(n logn) time
The approach using Merge Sort to count the number of inversions is detailed in this blog post ( https://codeground.in/blog/index.php...s-in-an-array/ ).

Was this useful? If you’re interested, you can read more about more such puzzles for Tech Interviews ( https://codeground.in/blog/index.php...iew-questions/ )or you can take do some online programming challenges ( https://codeground.in/screening-test...-contests.html )
Reply With Quote
Reply

Tags
count, general, inversions, thinking

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump


All times are GMT. The time now is 09:05 PM.


Powered by vBulletin® Version 3.7.2
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.

About Puzzle Baron

The Puzzle Baron family of web sites has served millions and millions of puzzle enthusiasts since its inception in 2006. From cryptograms to acrostics, logic puzzles to drop quotes, patchwords to wordtwist and even sudoku, we run the gamut in word puzzles, printable puzzles and logic games.