Logic Puzzle Forums Count Inversions
 FAQ Calendar Search Today's Posts Mark Forums Read

#1
11-22-2016, 12:44 AM
 CodeGroundOnlineTests Junior Member Join Date: Nov 2016 Posts: 8
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 )

 Tags count, general, inversions, thinking

 Thread Tools Display Modes Linear Mode

 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 User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Logic-Puzzles.org Discussion     Questions About Logic-Puzzles.org     Comments, Bugs and Feature Requests Other Logic Puzles     Logic Puzzles and Brain Benders Puzzle Baron's Logic Puzzles - The Book!

All times are GMT. The time now is 06:00 AM.