Python Program to Count Inversions with Explanation
Python
Hard
Functions
15 views
1 min read
91 words
This problem helps you practice core Python fundamentals in a practical way. It builds intuition around inversion, count, line. Let’s break it down step by step so you can implement it confidently.
Problem Statement
Read n integers. Use function mergesort_count(arr) to return inversion count and output it.
Input Format
First line n. Second line n integers.
Output Format
One integer inversions.
Constraints
1
Code Solution
This explanation is written for learning purposes and to help beginners understand the concept clearly.
import sys
sys.setrecursionlimit(1_000_000)
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
def sort_count(arr):
ln=len(arr)
if ln<=1:
return arr,0
mid=ln//2
left,inv1=sort_count(arr[:mid])
right,inv2=sort_count(arr[mid:])
i=0
j=0
inv=inv1+inv2
out=[]
while i<len(left) and j<len(right):
if left[i]<=right[j]:
out.append(left[i]); i+=1
else:
out.append(right[j]); j+=1
inv += len(left)-i
if i<len(left):
out.extend(left[i:])
if j<len(right):
out.extend(right[j:])
return out,inv
_,ans=sort_count(a)
sys.stdout.write(str(ans))
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Solution Guide
Problem
Read n integers. Use function mergesort_count(arr) to return inversion count and output it.
Input / Output
Input
First line n. Second line n integers.
Output
One integer inversions.
Details
Common Mistakes
- Misreading input/output format.
- Not handling constraints and edge cases.
- Off-by-one errors in loops.
- Forgetting to reset variables between test cases (if any).
Official Solution
import sys
sys.setrecursionlimit(1_000_000)
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
n=int(p[0])
a=list(map(int,p[1:1+n]))
def sort_count(arr):
ln=len(arr)
if ln<=1:
return arr,0
mid=ln//2
left,inv1=sort_count(arr[:mid])
right,inv2=sort_count(arr[mid:])
i=0
j=0
inv=inv1+inv2
out=[]
while i<len(left) and j<len(right):
if left[i]<=right[j]:
out.append(left[i]); i+=1
else:
out.append(right[j]); j+=1
inv += len(left)-i
if i<len(left):
out.extend(left[i:])
if j<len(right):
out.extend(right[j:])
return out,inv
_,ans=sort_count(a)
sys.stdout.write(str(ans))
Solutions (0)
No solutions submitted yet. Be the first!
