Iam_Sandeep

count no of inversions

Sep 16th, 2021 (edited)
1,033
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.83 KB | None | 0 0
  1. https://practice.geeksforgeeks.org/problems/inversion-of-array-1587115620/1
  2. Method 2:
  3. #concise
  4. class Solution:
  5.     def inversionCount(self, arr, n):
  6.         # Your Code Here
  7.         count=0
  8.         def merge(a):
  9.             nonlocal count
  10.             if len(a)==1 or 0:return a
  11.             mid=len(a)//2
  12.             L,R=a[:mid],a[mid:]
  13.             merge(L)
  14.             merge(R)
  15.             m,n=len(L),len(R)
  16.             i,j,k=0,0,0
  17.             while i<m and j<n:
  18.                 if L[i]<=R[j]:
  19.                     a[k]=L[i]
  20.                     i,k=i+1,k+1
  21.                 else:
  22.                     a[k]=R[j]
  23.                     count+=(m-i)
  24.                     j,k=j+1,k+1
  25.             while i<m:
  26.                 a[k]=L[i]
  27.                 i,k=i+1,k+1
  28.             while j<n:
  29.                 a[k]=R[j]
  30.                 j,k=j+1,k+1
  31.             return a
  32.         merge(arr)
  33.         return count
  34.  
  35. class Solution:
  36.     def inversionCount(self, arr, n):
  37.         global count
  38.         count=0
  39.         def merge(arr):
  40.             if len(arr)>1:
  41.                 global count
  42.                 mid=len(arr)//2
  43.                 L=arr[:mid]
  44.                 R=arr[mid:]
  45.                 merge(L)
  46.                 merge(R)
  47.                 m,n=len(L),len(R)
  48.                 i=j=0
  49.                 while i<m and j<n:#currently i and j are pointing to L,R
  50.                     if L[i]<=R[j]:
  51.                         '''
  52.                         Since we didnt find any inversion here , to get inversion pair we shall increment smaller one.
  53.                         i.e. i=i+1 . This is the same case down too. Just increase the smallest ones index.
  54.                         '''
  55.                    
  56.                         i=i+1
  57.                     else:
  58.                         '''
  59.                         Here you found L[i]>R[j] . Since R is sorted .all the numbers
  60.                         from 0....j are are less than L[i].
  61.                         Indirectly there are (m-i) inversion pairs. now here which is smaller?
  62.                         R[j] so increment that index i.e. j.
  63.                         '''
  64.                         count+=(m-i)
  65.                         j=j+1
  66.                  '''
  67.                 Now even if i is not eq to m or j is not eq n doesnt matter we have counted
  68.                 all inv pairs. Now just merge
  69.                 '''
  70.                        
  71.                 i=j=k=0
  72.                 #now do merge operation
  73.                 while i<m and j<n:
  74.                     if L[i]<R[j]:
  75.                         arr[k]=L[i]
  76.                         i=i+1
  77.                     else:
  78.                         arr[k]=R[j]
  79.                         j=j+1
  80.                     k=k+1
  81.                 while i<m:
  82.                     arr[k]=L[i]
  83.                     k=k+1
  84.                     i=i+1
  85.                 while j<n:
  86.                     arr[k]=R[j]
  87.                     k=k+1
  88.                     j=j+1
  89.         merge(arr)
  90.         return count
  91.                
  92.  
  93.                    
  94.                
  95.  
Advertisement
Add Comment
Please, Sign In to add comment