Hi @theghostyced . so I decided to try and solve this on my own and I want to share my insights
my first solution was to write some logic google the question and I came across a solution that didn't satisfy the complexity
def getInvCount(arr, n): inv_count = 0 for i in range(n): for j in range(i + 1, n): if (arr[i] > arr[j]): inv_count += 1 return inv_count
I then tried to rewrite this using list comprehension, you can see my effort here
def getInvCount(arr, n): return sum([1 if (arr[i] > arr[j]) else 0 for i in range(n) for j in range(i+1,n)])
but this also revealed the answers which you can use to solve this question.
Thanks @areahints but I think the time complexity still remains the same irrespective of the list comprehension.
yes, I mentioned that my list comprehension didn't satisfy the complexity.
consider this solution;
def getInvCount(arr,n): return mergeGetInvCount(arr)[1] def mergeGetInvCount(arr): if len(arr) <= 1: return arr, 0 middle = int(len(arr) / 2) left, a = mergeGetInvCount(arr[:middle]) right, b = mergeGetInvCount(arr[middle:]) result, c = mergeGetSplitInvCount(left, right) return result, (a + b + c) def mergeGetSplitInvCount(left, right): result = [] count = 0 i,j = 0,0 left_len = len(left) while i < left_len and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) count += left_len - i j += 1 result += left[i:] result += right[j:] return result, count # Driver Code arr = [1, 20, 6, 4, 5] n = len(arr) print("Number of inversions are", getInvCount(arr,n))
Number of inversions are 5
that's an O(n log n) implementation that I mentioned has been revealed in the link. did you read through it?
Are you sure you want to hide this comment? It will become hidden in your post, but will still be visible via the comment's permalink.
Hide child comments as well
Confirm
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Hi @theghostyced . so I decided to try and solve this on my own and I want to share my insights
my first solution was to
write some logicgoogle the question and I came across a solution that didn't satisfy the complexityI then tried to rewrite this using list comprehension, you can see my effort here
but this also revealed the answers which you can use to solve this question.
Thanks @areahints but I think the time complexity still remains the same irrespective of the list comprehension.
yes, I mentioned that my list comprehension didn't satisfy the complexity.
consider this solution;
Output
that's an O(n log n) implementation that I mentioned has been revealed in the link. did you read through it?