Given two integers N and K, the task is to find a permutation of first N natural numbers with exactly K inversions.
Examples :
Input: N = 5, K = 4
Output: 5 1 2 3 4
Explanation: In the above permutation P, the pairs (i, j) such that i < j and P[i] > P[j] are (0, 1), (0, 2), (0, 3), and (0, 4). Hence, the number of inversions in the above permutation is 4 which is the required value.Input: N = 3, K = 4
Output: -1
Explanation: No possible permutation of first 3 natural numbers has exactly 4 inversions.
Approach: The given problem can be solved by a Greedy Approach. It can be observed that if the maximum element of an array of N elements is assigned at ith position, it will contribute (N – i) inversions. Using this observation, follow the below steps to solve the given problem:
- Check for the condition whether K > the maximum number of possible inversions (i.e, N*(N-1)/2). If true, return -1.
- Create a variable curr, which keeps track of the current maximum element of the array. Initially curr = N.
- Create an array p[], which keeps track of the current permutation.
- Iterate using a variable i in the range [1, N], and if K > (curr – i), assign curr to the current position of the array and subtract (curr – i) from K. Also, decrement the value of curr by 1.
- If K > (curr – i) is false, assign K+1 to the current index and assign the remaining integers in increasing order in the array p[].
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the permutation of// N natural numbers with k inversionsvoid findPermutation(int n, int k){ // Stores the maximum number of inversions int max_inv = (n * (n - 1)) / 2; // If required inversions are more that max if (k > max_inv) { cout << "-1"; return; } // Stores the final permutation int p[n + 1]; // Keep track of the current max element // in the permutation int curr = n; int i = 1; // Loop to iterate through the array for (i = 1; i <= n; i++) { // Set current element as ith element // in order to increase n-i inversions // in the given permutation if (k >= n - i) { p[i] = curr; curr--; k -= (n - i); } // Otherwise set (k+1) element at ith index // ans assign the remaining indices else { // If the remaining inversion count is // greater than 0 if (k == 0) { i--; } else { p[i] = k + 1; } // Set the next index as 1 p[i + 1] = 1; // Loop to assign the remaining indices for (int j = i + 2; j <= n; j++) { p[j] = p[j - 1] + 1; // If current element already occurred if (p[i] == p[j]) { p[j]++; } } break; } } // Print Answer for (int j = 1; j <= n; j++) { cout << p[j] << " "; }}// Driver codeint main(){ int n = 5; int k = 4; findPermutation(n, k); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the permutation of// N natural numbers with k inversionsstatic void findPermutation(int n, int k){ // Stores the maximum number of inversions int max_inv = (n * (n - 1)) / 2; // If required inversions are more that max if (k > max_inv) { System.out.println("-1"); return; } // Stores the final permutation int [] p = new int[n+1]; // Keep track of the current max element // in the permutation int curr = n; int i = 1; // Loop to iterate through the array for (i = 1; i <= n; i++) { // Set current element as ith element // in order to increase n-i inversions // in the given permutation if (k >= n - i) { p[i] = curr; curr--; k -= (n - i); } // Otherwise set (k+1) element at ith index // ans assign the remaining indices else { // If the remaining inversion count is // greater than 0 if (k == 0) { i--; } else { p[i] = k + 1; } // Set the next index as 1 p[i + 1] = 1; // Loop to assign the remaining indices for (int j = i + 2; j <= n; j++) { p[j] = p[j - 1] + 1; // If current element already occurred if (p[i] == p[j]) { p[j]++; } } break; } } // Print Answer for (int j = 1; j <= n; j++) { System.out.print(p[j] + " "); }}// Driver code public static void main (String[] args) { int n = 5; int k = 4; findPermutation(n, k); }}// This code is contributed by Potta Lokesh |
Python3
# python program of the above approach# Function to find the permutation of# N natural numbers with k inversionsdef findPermutation(n, k): # Stores the maximum number of inversions max_inv = (n * (n - 1)) / 2 # If required inversions are more that max if (k > max_inv): print("-1") return # Stores the final permutation p = [0 for _ in range(n + 1)] # Keep track of the current max element # in the permutation curr = n i = 1 # Loop to iterate through the array for i in range(1, n+1): # Set current element as ith element # in order to increase n-i inversions # in the given permutation if (k >= n - i): p[i] = curr curr -= 1 k -= (n - i) # Otherwise set (k+1) element at ith index # ans assign the remaining indices else: # If the remaining inversion count is # greater than 0 if (k == 0): i -= 1 else: p[i] = k + 1 # Set the next index as 1 p[i + 1] = 1 # Loop to assign the remaining indices for j in range(i+2, n+1): p[j] = p[j - 1] + 1 # If current element already occurred if (p[i] == p[j]): p[j] += 1 break # Print Answer for j in range(1, n+1): print(p[j], end=" ")# Driver codeif __name__ == "__main__": n = 5 k = 4 findPermutation(n, k)# This code is contributed by rakeshsahni |
Javascript
<script> // JavaScript program of the above approach // Function to find the permutation of // N natural numbers with k inversions const findPermutation = (n, k) => { // Stores the maximum number of inversions let max_inv = (n * (n - 1)) / 2; // If required inversions are more that max if (k > max_inv) { document.write("-1"); return; } // Stores the final permutation let p = new Array(n + 1).fill(0); // Keep track of the current max element // in the permutation let curr = n; let i = 1; // Loop to iterate through the array for (i = 1; i <= n; i++) { // Set current element as ith element // in order to increase n-i inversions // in the given permutation if (k >= n - i) { p[i] = curr; curr--; k -= (n - i); } // Otherwise set (k+1) element at ith index // ans assign the remaining indices else { // If the remaining inversion count is // greater than 0 if (k == 0) { i--; } else { p[i] = k + 1; } // Set the next index as 1 p[i + 1] = 1; // Loop to assign the remaining indices for (let j = i + 2; j <= n; j++) { p[j] = p[j - 1] + 1; // If current element already occurred if (p[i] == p[j]) { p[j]++; } } break; } } // Print Answer for (let j = 1; j <= n; j++) { document.write(`${p[j]} `); } } // Driver code let n = 5; let k = 4; findPermutation(n, k); // This code is contributed by rakeshsahni</script> |
C#
// C# program for the above approachusing System;public class GFG { // Function to find the permutation of// N natural numbers with k inversionsstatic void findPermutation(int n, int k){ // Stores the maximum number of inversions int max_inv = (n * (n - 1)) / 2; // If required inversions are more that max if (k > max_inv) { Console.WriteLine("-1"); return; } // Stores the final permutation int [] p = new int[n+1]; // Keep track of the current max element // in the permutation int curr = n; int i = 1; // Loop to iterate through the array for (i = 1; i <= n; i++) { // Set current element as ith element // in order to increase n-i inversions // in the given permutation if (k >= n - i) { p[i] = curr; curr--; k -= (n - i); } // Otherwise set (k+1) element at ith index // ans assign the remaining indices else { // If the remaining inversion count is // greater than 0 if (k == 0) { i--; } else { p[i] = k + 1; } // Set the next index as 1 p[i + 1] = 1; // Loop to assign the remaining indices for (int j = i + 2; j <= n; j++) { p[j] = p[j - 1] + 1; // If current element already occurred if (p[i] == p[j]) { p[j]++; } } break; } } // Print Answer for (int j = 1; j <= n; j++) { Console.Write(p[j] + " "); }}// Driver code public static void Main (string[] args) { int n = 5; int k = 4; findPermutation(n, k); }}// This code is contributed by AnkThon |
Output
5 1 2 3 4
Time complexity: O(N)
Auxiliary Space: O(N)
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!
