Nope, ‘delta’ is the total number of inversions, while ‘sum’ is the sum of the degree of inversion of each node, and we define the degree of an index as the number of inversions in which it is present, so let’s take the example of 2 1, here the degree of inversion of each node is 1, so the sum would be 2, but the total number of inversions is 1. Thus, the total number of inversions is always half of the sum of degrees.
Nope we can’t say this, your statement implies that whenever we form a new array, the number of inversions will be preserved but that’s not the case. Example array 2 1, total number of inversions 1.
If broken into two arrays namely 2 and 1. Number of inversions in both arrays are 0.
So inv(a) + inv(b) != inv(arr)
yup I was about to mention that in my comment that equation doesn`t hold when no. of inversions is 1. but it’s not needed since the number of inversion in both separated arrays would still be totalinversion/2 that is (1/2=0). which is enough to solve the problem.
Still not true, the number of inversions doesn’t need to remain conserved.
Another example for you:
1 4 2 3
Number of inversions = 2
New arrays formed in accordance with the given ques.
1 4 & 2 3
The number of inversions in both new arrays are 0.
1 Like
thanks for correcting me.
why no solution follows memoization?