Given two integers N and K, the task is to generate a permutation of N numbers (Every number from 1 to N occurs exactly once) such that the number of indices where a[i]>a[i+1] is exactly K. Print “Not possible” if no such permutation is possible.
Examples:
Input: N = 5, K = 3 Output: 5 4 3 1 2 Starting 3 indices satisfying the condition a[i] > a[i]+1 Input: N = 7, k = 4 Output: 7 6 5 4 1 2 3
Approach: Since the permutation should be lexicographically smallest with the condition satisfied for k indices i.e. a[i] > a[i+1]. So for that starting K+1 digits should be in decreasing order and the remaining should be in increasing order. So just print the K numbers from N to 1. Then print numbers from 1 to N-K.
For example: N = 6, K = 4
Print K numbers from N to 1 i.e. 6, 5, 4, 3
Print N-K numbers from 1 to N-K i.e. 1, 2
Permutation will be 654312 i.e. Starting 4 indices satisfy a[i] > a[i+1] for i = 1 to k.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;void printPermutation(int n, int k){ int i, mx = n; for (i = 1; i <= k; i++) // Decreasing part { cout << mx << " "; mx--; } for (i = 1; i <= mx; i++) // Increasing part cout << i << " ";}// Driver Codeint main(){ int N = 5, K = 3; if (K >= N - 1) cout << "Not Possible"; else printPermutation(N, K); return 0;} |
Java
// Java implementation of the above approachimport java.io.*;class GFG {static void printPermutation(int n, int k){ int i, mx = n; for (i = 1; i <= k; i++) // Decreasing part { System.out.print( mx + " "); mx--; } for (i = 1; i <= mx; i++) // Increasing part System.out.print( i + " ");}// Driver Code public static void main (String[] args) { int N = 5, K = 3; if (K >= N - 1) System.out.print( "Not Possible"); else printPermutation(N, K); }}// This code is contributed by inder_verma.. |
Python3
# Python3 implementation of the# above approach def printPermutation(n, k): mx = n for i in range(1, k + 1): # Decreasing part print(mx, end = " ") mx -= 1 for i in range(1, mx + 1): # Increasing part print(i, end = " ") # Driver Code if __name__ == "__main__": N, K = 5, 3 if K >= N - 1: print("Not Possible") else: printPermutation(N, K) # This code is contributed# by Rituraj Jain |
C#
// C# implementation of the above approachusing System;class GFG {static void printPermutation(int n, int k){ int i, mx = n; for (i = 1; i <= k; i++) // Decreasing part { Console.Write( mx + " "); mx--; } for (i = 1; i <= mx; i++) // Increasing part Console.Write( i + " ");}// Driver Code public static void Main () { int N = 5, K = 3; if (K >= N - 1) Console.WriteLine( "Not Possible"); else printPermutation(N, K); }}// This code is contributed by inder_verma.. |
PHP
<?php// PHP implementation of the above approachfunction printPermutation($n, $k){ $i; $mx = $n; for ($i = 1; $i <=$k; $i++) // Decreasing part { echo $mx , " "; $mx--; } for ($i = 1; $i <=$mx; $i++) // Increasing part echo $i , " ";}// Driver Code $N = 5; $K = 3; if ($K >= $N - 1) echo "Not Possible"; else printPermutation($N, $K);// This code is contributed by inder_verma..?> |
Javascript
<script>// javascript implementation of the above approachfunction printPermutation(n , k){ var i, mx = n; for (i = 1; i <= k; i++) // Decreasing part { document.write( mx + " "); mx--; } for (i = 1; i <= mx; i++) // Increasing part document.write( i + " ");}// Driver Codevar N = 5, K = 3;if (K >= N - 1) document.write( "Not Possible");else printPermutation(N, K);// This code is contributed by 29AjayKumar </script> |
5 4 3 1 2
Time Complexity: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
