Given integers N and K, the task is to generate an array of length N which contains exactly K subarrays as a permutation of 1 to X where X is the subarray length. There may exist multiple answers you may print any one of them. If no array is possible to construct then print -1.
Note: A Permutation of length N is a list of integers from 1 to N(inclusive) where each element occurs exactly once.
Examples:
Input: N = 5, K = 4
Output: 1, 2, 3, 5, 4
Explanation: 4 subarrays which are a permutation of their own length are:
A[1] = {1}
A[1…2] = {1, 2}
A[1…3] = {1, 2, 3}
A[1…5] = {1, 2, 3, 5, 4}
Note that their exists no permutation of length 4 as a subarray.Input: N = 7, K = 3
Output: {1, 2, 7, 4, 5, 6, 3}
Explanation: 3 subarrays which are a permutation of their own length are:
A[1] = {1}
A[1…2] = {1, 2}
A[1…7] = {1, 2, 7, 3, 4, 5, 6}
Their exists no permutations of lengths 3, 4, 5 and 6 as a subarray.
Approach: The solution to the problem is based on the following observation. If all the numbers are arranged in increasing order from 1 to N then there are total N subarrays as permutations of their own length. If any value is swapped with the highest value then the number of permutations decreases. So to make the number same as K making the Kth value the highest and keeping the others increasingly sorted will fulfill the task. If N > 1 there are at least 2 subarrays which are permutation of their own length. Follow the steps mentioned below to solve the problem:
- If N > 1 and K < 2 or if K = 0 then no such array is possible.
- Generate an array of length N consisting of integers from 1 to N in sorted order.
- The maximum element in the array will obviously be the last element N which is arr[N-1].
- Swap arr[N-1] with arr[K-1]
- The array is one possible answer.
Illustration:
For example take N = 5, K = 4
- Generate array containing 1 to N is sorted order.
arr[] = {1, 2, 3, 4, 5}
There are 5 subarrays that are permutations of their own length: {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {1, 2, 3, 4, 5}- Here required K is 4. So swap the 4th element with the highest value.
arr[] = {1, 2, 3, 5, 4}
Now there are only K subarrays which are permutation of their own length: {1}, {1, 2}, {1, 2, 3}, {1, 2, 3, 4, 5}.
Because maximum value arrives at Kth position and now
for subarrays of length K or greater (but less than N) the highest element gets included in the subarray
which is not part of a permutation containing elements from 1 to X (subarray length).
Below is the implementation of the above approach.
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Function to generate the required arrayvector<int> generateArray(int N, int K){ vector<int> arr; // If making an array is not possible if (K == 0 || (N > 1 && K < 2)) return arr; arr.assign(N, 0); // Array of size N in sorted order for (int i = 1; i <= N; i++) arr[i - 1] = i; // Swap the maximum with the Kth element swap(arr[K - 1], arr[N - 1]); return arr;}// Driver codeint main(){ int N = 5, K = 4; // Function call vector<int> ans = generateArray(N, K); if (ans.size() == 0) cout << "-1"; else { for (int i : ans) cout << i << " "; } return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG{ // Function to swap two numbers static void swap(int m, int n) { // Swapping the values int temp = m; m = n; n = temp; } // Function to generate the required array static int[] generateArray(int N, int K) { int[] arr = new int[N]; // If making an array is not possible if (K == 0 || (N > 1 && K < 2)) return arr; for (int i = 0; i < N; i++) { arr[i] = 0; } // Array of size N in sorted order for (int i = 1; i <= N; i++) arr[i - 1] = i; // Swap the maximum with the Kth element swap(arr[K - 1], arr[N - 1]); return arr; } // Driver code public static void main(String[] args) { int N = 5, K = 4; // Function call int[] ans = generateArray(N, K); if (ans.length == 0) System.out.print("-1"); else { for (int i = 0; i < ans.length; i++) { System.out.print(ans[i] + " "); } } }}// This code is contributed by sanjoy_62. |
Python3
# Python program to implement the approach# Function to generate the required arraydef generateArray(N, K): arr = [] # If making an array is not possible if (K == 0 or (N > 1 and K < 2)): return arr for i in range(0, N): arr.append(0) # Array of size N in sorted order for i in range(1, N + 1): arr[i-1] = i # Swap the maximum with the Kth element arr[K - 1], arr[N - 1] = arr[N - 1], arr[K - 1] return arr# Driver codeN = 5K = 4# Function callans = generateArray(N, K)if (len(ans) == 0): print("-1")else: for i in ans: print(i, end=' ') # This code is contributed by ninja_hattori. |
C#
// C# program to implement the approachusing System;class GFG { // Function to swap two numbers static void swap(int m, int n) { // Swapping the values int temp = m; m = n; n = temp; } // Function to generate the required array static int[] generateArray(int N, int K) { int[] arr = new int[N]; // If making an array is not possible if (K == 0 || (N > 1 && K < 2)) return arr; for (int i = 0; i < N; i++) { arr[i] = 0; } // Array of size N in sorted order for (int i = 1; i <= N; i++) arr[i - 1] = i; // Swap the maximum with the Kth element swap(arr[K - 1], arr[N - 1]); return arr; } // Driver code public static void Main() { int N = 5, K = 4; // Function call int[] ans = generateArray(N, K); if (ans.Length == 0) Console.Write("-1"); else { for (int i = 0; i < ans.Length; i++) { Console.Write(ans[i] + " "); } } }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript code for the above approach// Function to generate the required arrayfunction generateArray( N, K){ let arr ; // If making an array is not possible if (K == 0 || (N > 1 && K < 2)) return []; arr = new Array(N).fill(0); // Array of size N in sorted order for (let i = 1; i <= N; i++) arr[i - 1] = i; // Swap the maximum with the Kth element let temp = arr[K - 1]; arr[K - 1] = arr[N-1]; arr[N-1] = temp return arr;}// Driver code let N = 5, K = 4; // Function call let ans = generateArray(N, K); if (ans.length == 0) document.write("-1"); else { for (let i of ans) document.write( i + " "); } // This code is contributed by Potta Lokesh </script> |
1 2 3 5 4
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
