Lexicographically smallest permutation with adjacent sum at least K
Given two positive integers N and K, the task is to find a permutation P of length N such that the sum of every adjacent pair of elements in P is greater than or equal to K. If there are multiple permutations that satisfy the condition, you should output the lexicographically smallest one. If there is no permutation that satisfies the condition, you should output -1.
Note: In other words, you need to find a permutation P of the numbers [1, 2, …, N] such that P[i] + P[i+1] ≥ K for all 1 ≤ i ≤ N-1. The lexicographically smallest permutation is the one that comes first in alphabetical order when the numbers are written out in sequence. For example, [1, 2, 3] is lexicographically smaller than [1, 3, 2].
Examples:
Input: N = 6, K = 5
Output: 1 4 2 3 5 6
Explanation: Considering the permutation 1 4 2 3 5 6 sum of adjacent elements is greater than 5. There exists different permutation such as [3, 5, 1, 4, 2, 6], [1, 5, 2, 3, 4, 6], [6, 1, 4, 3, 5, 6]etc. But
[1, 4, 2, 3, 5, 6] is the lexicographically smallest one among them.Input: N = 4, K = 6
Output: -1
Explanation: No such permutation exists which satisfies the above condition.
Approach: To solve the problem follow the below idea:
The idea is to first store K-1 numbers, starting with K, in descending order, at even indices of the array, and then store the remaining numbers in ascending order at odd indices of the array. Finally, any remaining indices are filled with the natural sequence of numbers.
Below are the steps for the above approach:
- Check if N is less than K. If so then no permutation can be generated which satisfies the above condition so print -1 and return.
- Create a vector say a to store the answer.
- Initialize two variables x = –K and y = 2.
- Increment k to the original value.
- Run a loop from i = 0 to i ≤ N,
- Check if i > 1 and i < K,
- Check if i%2 == 0, add the value x to the resultant vector a, and decrement x by 1.
- Else, add the value y to the resultant vector a, and increment y by 1.
- Else, add i to the resultant vector.
- Check if i > 1 and i < K,
C++
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; void Generatepermutation( int n, int k) { // Check if n is less than k. If so // then no permutation can be generated // which satisfies above condition so // print -1 and return. if (n < k - 1) { cout << -1 << endl; return ; } // Create a vector to store the answer vector< int > a; // Store k-1 number to store values in // descending order in even indices int x = --k; // Start with 2 to store values in // ascending order in odd indices int y = 2; // Increment k to original value k++; // Iterate till n for ( int i = 1; i <= n; i++) { // To store values in the // range from 2 to k-1 if (i > 1 && i < k) { // Store values in even // indices of array if (i % 2 == 0) { a.push_back(x); x--; } else { a.push_back(y); y++; } } else { // Store values according to // natural sequence in array a.push_back(i); } } // Print the permutation generated for ( int i = 0; i < a.size(); i++) { cout << a[i] << " " ; } cout << endl; } // Drivers code int main() { int N = 6, K = 5; // Function call Generatepermutation(N, K); return 0; } |
Java
// Java Program for the above approach import java.io.*; import java.util.*; class GFG { public static void Generatepermutation( int n, int k) { // Check if n is less than k. If so // then no permutation can be generated // which satisfies above condition so // print -1 and return. if (n < k - 1 ) { System.out.println(- 1 ); return ; } // Create a vector to store the answer ArrayList<Integer> a = new ArrayList<Integer>(); // Store k-1 number to store values in // descending order in even indices int x = --k; // Start with 2 to store values in // ascending order in odd indices int y = 2 ; // Increment k to original value k++; // Iterate till n for ( int i = 1 ; i <= n; i++) { // To store values in the // range from 2 to k-1 if (i > 1 && i < k) { // Store values in even // indices of array if (i % 2 == 0 ) { a.add(x); x--; } else { a.add(y); y++; } } else { // Store values according to // natural sequence in array a.add(i); } } // Print the permutation generated for ( int i = 0 ; i < a.size(); i++) { System.out.print(a.get(i) + " " ); } System.out.println(); } // Driver Code public static void main(String[] args) { int N = 6 , K = 5 ; // Function call Generatepermutation(N, K); } } // This code is contributed by Rohit Pradhan |
Python3
# Python Program for the above approach def Generatepermutation(n, k): # Check if n is less than k. If so # then no permutation can be generated # which satisfies above condition so # print -1 and return. if n < k - 1 : print ( - 1 ) return # Create a vector to store the answer a = [] # Store k-1 number to store values in # descending order in even indices x = k - 1 # Start with 2 to store values in # ascending order in odd indices y = 2 # Iterate till n for i in range ( 1 , n + 1 ): # To store values in the # range from 2 to k-1 if i > 1 and i < k: # Store values in even # indices of array if i % 2 = = 0 : a.append(x) x - = 1 else : a.append(y) y + = 1 else : # Store values according to # natural sequence in array a.append(i) # Print the permutation generated for i in range ( len (a)): print (a[i], end = " " ) print () # Driver code if __name__ = = '__main__' : N = 6 K = 5 # Function call Generatepermutation(N, K) # This code is contributed by Tapesh(tapeshdua420) |
C#
// C# Program for the above approach using System; using System.Collections.Generic; class Program { static void GeneratePermutation( int n, int k) { // Check if n is less than k. If so // then no permutation can be generated // which satisfies above condition so // print -1 and return. if (n < k - 1) { Console.WriteLine(-1); return ; } // Create a vector to store the answer List< int > a = new List< int >(); // Store k-1 number to store values in // descending order in even indices int x = --k; // Start with 2 to store values in // ascending order in odd indices int y = 2; // Increment k to original value k++; // Iterate till n for ( int i = 1; i <= n; i++) { // To store values in the // range from 2 to k-1 if (i > 1 && i < k) { // Store values in even // indices of array if (i % 2 == 0) { a.Add(x); x--; } else { a.Add(y); y++; } } else { // Store values according to // natural sequence in array a.Add(i); } } // Print the permutation generated foreach ( int num in a) { Console.Write(num + " " ); } Console.WriteLine(); } // Driver Code static void Main( string [] args) { int N = 6, K = 5; GeneratePermutation(N, K); } } //This Program is contributed by Shivam Tiwari |
Javascript
function Generatepermutation(n, k) { // Check if n is less than k. If so // then no permutation can be generated // which satisfies above condition so // print -1 and return. if (n < k - 1) { console.log(-1); return ; } // Create a array to store the answer let a = []; // Store k-1 number to store values in // descending order in even indices let x = --k; // Start with 2 to store values in // ascending order in odd indices let y = 2; // Increment k to original value k++; // Iterate till n for (let i = 1; i <= n; i++) { // To store values in the // range from 2 to k-1 if (i > 1 && i < k) { // Store values in even // indices of array if (i % 2 == 0) { a.push(x); x--; } else { a.push(y); y++; } } else { // Store values according to // natural sequence in array a.push(i); } } // Print the permutation generated console.log(a.join( " " )); } // Drivers code let N = 6, K = 5; // Function call Generatepermutation(N, K); // This Code is Contributed by Shivam Tiwari |
1 4 2 3 5 6
Time Complexity: O(N)
Auxiliary Space: O(N)