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 permutationvoid 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 Codeint main(){ int N = 3; int K = 1; permutation(N, K); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;public class GFG{// Function to print permutationstatic 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 Codepublic 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 permutationdef 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 CodeN = 3;K = 1;permutation(N, K);# This code is contributed by Saurabh Jaiswal |
C#
// C# program to implement// the above approachusing 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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
