# Is there an efficient way to solve this problem?

Given a series of n numbers, I need an algorithm that runs in worst case O(n*k) to figure out how many arrangements of those n numbers will give me a score of exactly k.

Note that the series does not contain duplicate elements.

The score of a series of numbers is calculated by the number of smaller numbers an element in the series has before it.

For example, The score of the below series would be:

series = [5,3,6]

5 has no smaller number before it, so 0

3 has no smaller number before it, so 0

6 has 2 smaller numbers before it (5,3) so 2

Adding all of this, we get a total score for the series as 2.

What I have tried to do:

I have tried to find all possible arrangements of the series -> (n! many arrangements)

and count the ones that have a score of k.

But this has a worst case time complexity of O(n!). Any help/ideas will be much appreciated. Thanks!

• Are numbers all different or could there be duplicates? Commented Nov 8, 2022 at 13:16
• @Nathaniel No duplicates, all different Commented Nov 8, 2022 at 13:18
• As the numbers are all different you are counting permutations with k inversions. Commented Nov 8, 2022 at 17:15

Note that the values contained in the series are not important, and you can consider those values are exactly $$1, 2, …, n$$ (because only relative order is important).

Denote $$A(n, k)$$ the number of arrangements of $$n$$ values to reach score $$k$$.

Given an arrangement of $$n$$ values of score $$k$$, if you add the value $$n+1$$, you can:

• put it in first position and not change the score;
• put it in second position and add one to the score;
• put it in last position and add $$n$$ to the score.

Considering all this, we get the induction formula: $$A(n+1, k) = \sum\limits_{i = 0}^n A(n, k - i)$$ The base cases are:

• $$A(1, 0) = 1$$;
• $$A(n, k) = 0$$ if $$k < 0$$.

The total runtime of dynamic programming algorithm computing this would be $$\mathcal{O}(n^2k) = \mathcal{O}(n^2)$$ if $$k$$ is considered a constant.

There may be a closed formula that could be used to compute this in $$\mathcal{O}(1)$$, but I don't know it.

• is there a way to do this in O(n*k) time? Commented Nov 9, 2022 at 0:21
• @brownturtle, Given $A(n,0), \ldots, A(n,k)$, you can compute $A(n+1,0), \ldots, A(n+1, k)$ in $O(k)$ time based on the recurrent expression in the post (it's a simple exercise, one way is to do some preprocessing on $A(n,0), \ldots, A(n,k)$). Also, from this recurrence, you can derive another recurrence of the form $A(n+1,k+1) = A(n+1,k) + \ldots$, which also makes it clear how to get $O(k)$ time. Commented Nov 9, 2022 at 1:03