Find Permutation of N numbers in range [1, N] such that K numbers have value same as their index
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 Ai = 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 Ai = 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 Ai = 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> |
1 3 2
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us