The problem
A timetable lists trains in the order they are booked to leave. The list a holds the order in which they really left. Count how far out of order it is: the number of inversions, pairs of positions i < j with a[i] > a[j].
count_inversions([2, 4, 1, 3, 5])
# 3: (2, 1), (4, 1), (4, 3)
count_inversions([5, 4, 3, 2, 1]) # 10
count_inversions([2, 2, 1])
# 2: equal values are not out of order
Limits
- Up to 100,000 values. The answer can be up to about 5 billion; Python’s whole numbers handle that.
Builds on SORT-2 Merge sort.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
6 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | A few | Not run | |
| 2 | Sorted | Not run | |
| 3 | Reversed | Not run | |
| 4 | Equal values | Not run | |
| 5 | Empty and one | Not run | |
| 6 | 100,000 values | Not run |