Given two integers N and K, the task is to count the number of permutations of the first N natural numbers having exactly K inversions. Since the count can be very large, print it modulo 109 + 7.
An inversion is defined as a pair a[i], a[j] such that a[i] > a[j] and i < j.
Examples:
Input: N = 3, K = 2
Output: 2
Explanation:
All Permutations for N = 3 are 321, 231, 213, 312, 132, 123.
Out of which only 231 and 312 have 2 inversions as:
- 231: 2 > 1 & 3 > 1
- 312: 3 > 1 & 3 > 2.
Therefore, both are satisfying the condition of having exactly K inversions.
Input: N = 5, K = 5
Output: 22
Â
Naive Approach: Refer to the previous post for the simplest possible approach to solve the problem.Â
Time Complexity: O(N*N!)
Auxiliary Space: O(1)
Dynamic Programming using Top-Down Approach: Refer to the previous post of this article for the Top-Down Approach.Â
Time Complexity: O(N*K2)
Auxiliary Space: O(N*K)
Dynamic Programming using Bottom-Up Approach:
Illustration:
For Example: N = 4, K = 2
N – 1 = 3, K0 = 0 …  123      =>  1423
N – 1 = 3, K1 = 1 …  213, 132  =>  2143, 1342
N – 1 = 3, K2 = 2 …  231, 312  =>  2314, 3124
So the answer is 5.The maximum value is taken between (K – N + 1) and 0 as K inversions cannot be obtained if the number of inversions in permutation of (N – 1) numbers is less than K – (N – 1) as at most (N – 1) new inversions can be obtained by adding Nth number at the beginning.
Follow the steps below to solve the problem:
- Create an auxiliary array dp[2][K + 1] where dp[N][K] stores all permutations of (N – 1) numbers with K = (max(K – (N – 1), 0) to K) inversions, by adding Nth number with them only once.
- Using dp[i % 2][K] will interchange iteration between two rows and take j = Max(K – (N – 1), 0). So dp[N[K] = dp[N-1][j] + dp[N-1][j+1] + …. + dp[N – 1][K].
- For calculating dp[N][K] there is no need to do this extra K iteration as it can be obtained in O(1) from dp[N][K – 1]. So the recurrence relation is given by:
- dp[N][K] = dp[N][K – 1] + dp[N – 1][K] – dp[N – 1][max(K – (N – 1), 0) – 1]
- Iterate two nested loops using the variable i and j over N and K respectively and update each dp states as per the above recurrence relation.
- Print the value of dp[N%2][K] after the above steps as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach   #include <bits/stdc++.h> using namespace std;   // Function to count permutations with // K inversions int numberOfPermWithKInversion(     int N, int K) {     // Store number of permutations     // with K inversions     int dp[2][K + 1];       int mod = 1000000007;       for (int i = 1; i <= N; i++) {         for (int j = 0; j <= K; j++) {               // If N = 1 only 1 permutation             // with no inversion             if (i == 1)                 dp[i % 2][j] = (j == 0);               // For K = 0 only 1 permutation             // with no inversion             else if (j == 0)                 dp[i % 2][j] = 1;               // Otherwise Update each dp             // state as per the reccurrance             // relation formed             else                dp[i % 2][j]                     = (dp[i % 2][j - 1] % mod                        + (dp[1 - i % 2][j]                           - ((max(j - (i - 1), 0) == 0)                                  ? 0                                  : dp[1 - i % 2]                                      [max(j - (i - 1), 0)                                       - 1])                           + mod)                              % mod)                       % mod;             ;         }     }       // Print final count     cout << dp[N % 2][K]; }   // Driver Code int main() {     // Given N and K     int N = 3, K = 2;       // Function Call     numberOfPermWithKInversion(N, K);       return 0; } |
Java
// Java program for the above approach import java.io.*;   class GFG{   // Function to count permutations with // K inversions static void numberOfPermWithKInversion(int N, int K) {           // Store number of permutations     // with K inversions     int[][] dp = new int[2][K + 1];       int mod = 1000000007;       for(int i = 1; i <= N; i++)     {         for(int j = 0; j <= K; j++)         {                           // If N = 1 only 1 permutation             // with no inversion             if (i == 1)             {                 dp[i % 2][j] = (j == 0) ? 1 : 0;             }               // For K = 0 only 1 permutation             // with no inversion             else if (j == 0)                 dp[i % 2][j] = 1;               // Otherwise Update each dp             // state as per the reccurrance             // relation formed             else                {                  int maxm = Math.max(j - (i - 1));              dp[i % 2][j] = (dp[i % 2][j - 1] % mod +                                (dp[1 - i % 2][j] -                                ((Math.max(j - (i - 1), 0) == 0) ?                                    0 : dp[1 - i % 2][maxm, 0) - 1]) +                                          mod) % mod) % mod; }         }     }           // Print final count     System.out.println (dp[N % 2][K]); }   // Driver Code public static void main(String[] args) {           // Given N and K     int N = 3, K = 2;       // Function Call     numberOfPermWithKInversion(N, K); } }   // This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach   # Function to count permutations with # K inversions def numberOfPermWithKInversion(N, K):           # Store number of permutations     # with K inversions     dp = [[0] * (K + 1)] * 2      mod = 1000000007      for i in range(1, N + 1):         for j in range(0, K + 1):                           # If N = 1 only 1 permutation             # with no inversion             if (i == 1):                 dp[i % 2][j] = 1 if (j == 0) else 0              # For K = 0 only 1 permutation             # with no inversion             elif (j == 0):                 dp[i % 2][j] = 1              # Otherwise Update each dp             # state as per the reccurrance             # relation formed             else:                 var = (0 if (max(j - (i - 1), 0) == 0)                          else dp[1 - i % 2][max(j - (i - 1), 0) - 1])                 dp[i % 2][j] = ((dp[i % 2][j - 1] % mod +                                (dp[1 - i % 2][j] -                                (var) + mod) % mod) % mod)       # Print final count     print(dp[N % 2][K])   # Driver Code if __name__ == '__main__':           # Given N and K     N = 3    K = 2      # Function Call     numberOfPermWithKInversion(N, K)   # This code is contributed by akhilsaini |
C#
// C# program for the above approach using System;   class GFG{   // Function to count permutations with // K inversions static void numberOfPermWithKInversion(int N, int K) {           // Store number of permutations     // with K inversions     int[,] dp = new int[2, K + 1];       int mod = 1000000007;       for(int i = 1; i <= N; i++)     {         for(int j = 0; j <= K; j++)         {                           // If N = 1 only 1 permutation             // with no inversion             if (i == 1)             {                 dp[i % 2, j] = (j == 0) ? 1 : 0;             }               // For K = 0 only 1 permutation             // with no inversion             else if (j == 0)                 dp[i % 2, j] = 1;               // Otherwise Update each dp             // state as per the reccurrance             // relation formed             else                dp[i % 2, j] = (dp[i % 2, j - 1] % mod +                                (dp[1 - i % 2, j] -                                ((Math.Max(j - (i - 1), 0) == 0) ?                                    0 : dp[1 - i % 2, Math.Max(                                           j - (i - 1), 0) - 1]) +                                               mod) % mod) % mod;         }     }       // Print final count     Console.WriteLine(dp[N % 2, K]); }   // Driver Code public static void Main() {       // Given N and K     int N = 3, K = 2;       // Function Call     numberOfPermWithKInversion(N, K); } }   // This code is contributed by akhilsaini |
Javascript
<script>   // Javascript program to implement // the above approach   // Function to count permutations with // K inversions function numberOfPermWithKInversion(N, K) {             // Store number of permutations     // with K inversions     let dp = new Array(2);     // Loop to create 2D array using 1D array     for (var i = 0; i < dp.length; i++)     {     dp[i] = new Array(2);     }         let mod = 1000000007;         for(let i = 1; i <= N; i++)     {         for(let j = 0; j <= K; j++)         {                             // If N = 1 only 1 permutation             // with no inversion             if (i == 1)             {                 dp[i % 2][j] = (j == 0) ? 1 : 0;             }                 // For K = 0 only 1 permutation             // with no inversion             else if (j == 0)                 dp[i % 2][j] = 1;                 // Otherwise Update each dp             // state as per the reccurrance             // relation formed             else                dp[i % 2][j] = (dp[i % 2][j - 1] % mod +                  (dp[1 - i % 2][j] -                  ((Math.max(j - (i - 1), 0) == 0) ?                    0 : dp[1 - i % 2][(Math.max(j -                           (i - 1), 0) - 1)]) +                              mod) % mod) % mod;         }     }             // Print final count     document.write(dp[N % 2][K]); }           // Driver Code                   // Given N and K     let N = 3, K = 2;         // Function Call     numberOfPermWithKInversion(N, K);     </script> |
Â
Â
Output:Â
2
Â
Â
Time Complexity: O(N * K)
Auxiliary Space: O(K)
Â
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
