Find Permutation of N numbers in range [1, N] such that K numbers have value same as their index

0 0 4 minutes read

Given a positive integer N and an integer K such that 0 ≤ K ≤ N, the task is to find any permutation A of [1, N] such that the number of indices for which A_i = i is exactly K (1-based indexing). If there exists no such permutation, print −1.

Examples:

Input: N = 3, K = 1
Output: 1 3 2
Explanation: Consider the permutation A = [1, 3, 2]. We have A1=1, A2=3 and A3=2.
So, this permutation has exactly 1 index such that A_i= i.

Input: N = 2, K = 1
Output: -1
Explanation : There are total 2 permutations of [1, 2] which are [1, 2] and [2, 1].
There are 2 indices in [1, 2] and 0 indices in [2, 1] for which A_i= i holds true.
Thus, there doesn’t exist any permutation of [1, 2] with exactly 1 index i for which Ai=i holds true.

Approach: The task can be solved using the greedy approach. Initially fix exactly K elements at their indices and then just randomly put N-K elements at different places. Follow the below steps to solve the problem:

Somehow fix K positions
Dislocate remaining N-K numbers
Cyclic shift remaining element by one

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to print permutation
void permutation(int N, int K)
{
    if (K == N) {
        for (int i = 1; i <= N; i++) {
            cout << i << ' ';
        }
        cout << '\n';
    }
    else if (K == N - 1) {
        cout << "-1" << '\n';
    }
    else {
        for (int i = 1; i <= K; i++) {
            cout << i << ' ';
        }
        for (int i = K + 2; i <= N; i++) {
            cout << i << ' ';
        }
        cout << K + 1 << '\n';
    }
}
 
// Driver Code
int main()
{
    int N = 3;
    int K = 1;
    permutation(N, K);
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
public class GFG
{
 
// Function to print permutation
static void permutation(int N, int K)
{
    if (K == N) {
        for (int i = 1; i <= N; i++) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    else if (K == N - 1) {
        System.out.println("-1");
    }
    else {
        for (int i = 1; i <= K; i++) {
            System.out.print(i + " ");
        }
        for (int i = K + 2; i <= N; i++) {
            System.out.print(i + " ");
        }
        System.out.println(K + 1);
    }
}
 
// Driver Code
public static void main(String args[])
{
    int N = 3;
    int K = 1;
    permutation(N, K);
}
}
 
// This code is contributed by Samim Hossain Mondal.

Python3

# Python code for the above approach
 
# Function to print permutation
def permutation(N, K):
    if (K == N):
        for i in range(1, N + 1):
            print(i, end=" ")
        print('')
    elif (K == N - 1):
        print(-1)
    else:
        for i in range(1, K + 1):
            print(i, end=" ")
        for i in range(K + 2, N + 1):
            print(i, end=" ")
        print(K + 1)
 
# Driver Code
N = 3;
K = 1;
permutation(N, K);
 
# This code is contributed by Saurabh Jaiswal

C#

// C# program to implement
// the above approach
using System;
public class GFG {
 
  // Function to print permutation
  static void permutation(int N, int K)
  {
    if (K == N) {
      for (int i = 1; i <= N; i++) {
        Console.Write(i + " ");
      }
      Console.WriteLine();
    }
    else if (K == N - 1) {
      Console.WriteLine("-1");
    }
    else {
      for (int i = 1; i <= K; i++) {
        Console.Write(i + " ");
      }
      for (int i = K + 2; i <= N; i++) {
        Console.Write(i + " ");
      }
      Console.Write(K + 1);
    }
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 3;
    int K = 1;
    permutation(N, K);
  }
}
 
// This code is contributed by ukasp.

Javascript

<script>
      // JavaScript code for the above approach
 
      // Function to print permutation
      function permutation(N, K) {
          if (K == N) {
              for (let i = 1; i <= N; i++) {
                  document.write(i + " ")
              }
              document.write('<br>')
          }
          else if (K == N - 1) {
              document.write(-1 + '<br>')
          }
          else {
              for (let i = 1; i <= K; i++) {
                  document.write(i + " ")
              }
              for (let i = K + 2; i <= N; i++) {
                  document.write(i + " ")
              }
              document.write(K + 1 + '<br>')
          }
      }
 
      // Driver Code
      let N = 3;
      let K = 1;
      permutation(N, K);
 
// This code is contributed by Potta Lokesh
  </script>

Output

1 3 2

Time Complexity: O(N)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!