Lexicographically Smallest Permutation of length N such that for exactly K indices, a[i] > a[i] + 1

0 0 3 minutes read

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 Code
int 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 approach
 
import 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 approach
using 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 approach
 
function 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 approach
function 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 Code
var N = 5, K = 3;
 
if (K >= N - 1)
    document.write( "Not Possible");
 
else
    printPermutation(N, K);
 
// This code is contributed by 29AjayKumar 
</script>

Output

5 4 3 1 2

Time Complexity: 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 zambiatek!