Generate a permutation of first N natural numbers having count of unique adjacent differences equal to K
Given two positive integers N and K, the task is to construct a permutation of the first N natural numbers such that all possible absolute differences between adjacent elements is K.
Examples:
Input: N = 3, K = 1
Output: 1 2 3
Explanation: Considering the permutation {1, 2, 3}, all possible unique absolute difference of adjacent elements is {1}. Since the count is 1(= K), print the sequence {1, 2, 3} as the resultant permutation.Input: N = 3, K = 2
Output: 1 3 2
Naive Approach: The simplest approach to solve the given problem is to create an array with elements from 1 to N arranged in ascending order and then traverse the first K elements of the array and reverse the subarray starting at the current index and ending at the last index. After completing the above steps, print the resultant array obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to reverse the given list void reverse( int list[], int start, int end) { // Iterate until start < end while (start < end) { // Swap operation int temp = list[start]; list[start] = list[end]; list[end] = temp; start++; end--; } } // Function to construct a list with // exactly K unique adjacent element // differences void makeList( int N, int K) { // Stores the resultant array int list[N]; // Add initial value to array for ( int i = 1; i <= N; i++) { list[i - 1] = i; } // Reverse the list k-1 times // from index i to n-1 for ( int i = 1; i < K; i++) { reverse(list, i, N - 1); } // Print the resultant array for ( int i = 0; i < N; i++) { cout << list[i] << " " ; } } // Driver code int main() { int N = 6, K = 3; makeList(N, K); return 0; } // This code is contributed by mohit kumar 29 |
Java
// Java program for the above approach class GFG { // Function to construct a list with // exactly K unique adjacent element // differences public static void makeList( int N, int K) { // Stores the resultant array int [] list = new int [N]; // Add initial value to array for ( int i = 1 ; i <= N; i++) { list[i - 1 ] = i; } // Reverse the list k-1 times // from index i to n-1 for ( int i = 1 ; i < K; i++) { reverse(list, i, N - 1 ); } // Print the resultant array for ( int i = 0 ; i < list.length; i++) { System.out.print(list[i] + " " ); } } // Function to reverse the given list public static void reverse( int [] list, int start, int end) { // Iterate until start < end while (start < end) { // Swap operation int temp = list[start]; list[start] = list[end]; list[end] = temp; start++; end--; } } // Driver Code public static void main( String[] args) { int N = 6 , K = 3 ; makeList(N, K); } } |
Python3
# Python 3 program for the above approach # Function to reverse the given lst def reverse(lst, start, end): # Iterate until start < end while (start < end): # Swap operation temp = lst[start] lst[start] = lst[end] lst[end] = temp start + = 1 end - = 1 # Function to construct a lst with # exactly K unique adjacent element # differences def makelst(N, K): # Stores the resultant array lst = [ 0 for i in range (N)] # Add initial value to array for i in range ( 1 , N + 1 , 1 ): lst[i - 1 ] = i # Reverse the lst k-1 times # from index i to n-1 for i in range ( 1 , K, 1 ): reverse(lst, i, N - 1 ) # Print the resultant array for i in range (N): print (lst[i], end = " " ) # Driver code if __name__ = = '__main__' : N = 6 K = 3 makelst(N, K) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; class GFG{ // Function to construct a list with // exactly K unique adjacent element // differences public static void makeList( int N, int K) { // Stores the resultant array int [] list = new int [N]; // Add initial value to array for ( int i = 1; i <= N; i++) { list[i - 1] = i; } // Reverse the list k-1 times // from index i to n-1 for ( int i = 1; i < K; i++) { reverse(list, i, N - 1); } // Print the resultant array for ( int i = 0; i < list.Length; i++) { Console.Write(list[i] + " " ); } } // Function to reverse the given list public static void reverse( int [] list, int start, int end) { // Iterate until start < end while (start < end) { // Swap operation int temp = list[start]; list[start] = list[end]; list[end] = temp; start++; end--; } } // Driver Code static public void Main() { int N = 6, K = 3; makeList(N, K); } } // This code is contributed by Dharanendra L V. |
Javascript
<script> // Javascript program for the above approach // Function to construct a list with // exactly K unique adjacent element // differences function makeList(N, K) { // Stores the resultant array let list = Array.from(Array(N), ()=>Array(0)); // Add initial value to array for (let i = 1; i <= N; i++) { list[i - 1] = i; } // Reverse the list k-1 times // from index i to n-1 for (let i = 1; i < K; i++) { reverse(list, i, N - 1); } // Print the resultant array for (let i = 0; i < list.length; i++) { document.write(list[i] + " " ); } } // Function to reverse the given list function reverse( list, start, end) { // Iterate until start < end while (start < end) { // Swap operation let temp = list[start]; list[start] = list[end]; list[end] = temp; start++; end--; } } // Driver Code let N = 6, K = 3; makeList(N, K); // This code is contributed by sanjoy_62. </script> |
1 6 2 3 4 5
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The above approach can also be optimized by using the two-pointer approach. Follow the steps below to solve the problem:
- Initialize an array ans[] of size N, that stores the resultant permutation.
- Create two variables, say left and right as 1 and N respectively.
- Traverse the given array and perform the following steps:
- If the value of K is even, then push the value of the left to the array ans[] and increment the value of left by 1.
- If the value of K is odd, then push the value of the right to the array ans[] and decrement the value of right by 1.
- If the value of K is greater than 1, then decrement the value of K by 1.
- After completing the above steps, print the array ans[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include<bits/stdc++.h> using namespace std; // Function to construct the list // with exactly K unique adjacent // element differences void makeList( int N, int K) { // Stores the resultant array int list[N]; // Stores the left and the right // most element of the range int left = 1; int right = N; // Traverse the array for ( int i = 0; i < N; i++) { // If k is even, the add // left to array and // increment the left if (K % 2 == 0) { list[i] = left; left = left + 1; } // If k is odd, the add // right to array and // decrement the right else { list[i] = right; right = right - 1; } // Repeat the steps for // k-1 times if (K > 1) K--; } // Print the resultant list for ( int i = 0; i < N; i++) { cout<<list[i]<< " " ; } } // Driver Code int main() { int N = 6; int K = 3; makeList(N, K); } // This code is contributed by ukasp. |
Java
// Java program for the above approach class GFG { // Function to construct the list // with exactly K unique adjacent // element differences public static void makeList( int N, int K) { // Stores the resultant array int [] list = new int [N]; // Stores the left and the right // most element of the range int left = 1 ; int right = N; // Traverse the array for ( int i = 0 ; i < N; i++) { // If k is even, the add // left to array and // increment the left if (K % 2 == 0 ) { list[i] = left; left = left + 1 ; } // If k is odd, the add // right to array and // decrement the right else { list[i] = right; right = right - 1 ; } // Repeat the steps for // k-1 times if (K > 1 ) K--; } // Print the resultant list for ( int i = 0 ; i < list.length; i++) { System.out.print( list[i] + " " ); } } // Driver Code public static void main(String[] args) { int N = 6 ; int K = 3 ; makeList(N, K); } } |
Python3
# Python3 program for the above approach # Function to construct the lst # with exactly K unique adjacent # element differences def makelst(N, K): # Stores the resultant array lst = [ 0 for i in range (N)] # Stores the left and the right # most element of the range left = 1 right = N # Traverse the array for i in range (N): # If k is even, the add # left to array and # increment the left if (K % 2 = = 0 ): lst[i] = left left = left + 1 # If k is odd, the add # right to array and # decrement the right else : lst[i] = right right = right - 1 # Repeat the steps for # k-1 times if (K > 1 ): K - = 1 # Print the resultant lst for i in range (N): print (lst[i], end = " " ) # Driver Code if __name__ = = '__main__' : N = 6 K = 3 makelst(N, K) # This code is contributed by bgangwar59 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Function to construct the list // with exactly K unique adjacent // element differences public static void makeList( int N, int K) { // Stores the resultant array int [] list = new int [N]; // Stores the left and the right // most element of the range int left = 1; int right = N; // Traverse the array for ( int i = 0; i < N; i++) { // If k is even, the add // left to array and // increment the left if (K % 2 == 0) { list[i] = left; left = left + 1; } // If k is odd, the add // right to array and // decrement the right else { list[i] = right; right = right - 1; } // Repeat the steps for // k-1 times if (K > 1) K--; } // Print the resultant list for ( int i = 0; i < list.Length; i++) { Console.Write(list[i] + " " ); } } // Driver Code public static void Main(String[] args) { int N = 6; int K = 3; makeList(N, K); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach // Function to construct the list // with exactly K unique adjacent // element differences function makeList(N, K) { // Stores the resultant array var list= new Array(N); // Stores the left and the right // most element of the range var left = 1; var right = N; // Traverse the array for ( var i = 0; i < N; i++) { // If k is even, the add // left to array and // increment the left if (K % 2 == 0) { list[i] = left; left = left + 1; } // If k is odd, the add // right to array and // decrement the right else { list[i] = right; right = right - 1; } // Repeat the steps for // k-1 times if (K > 1) K--; } // Print the resultant list for ( var i = 0; i < N; i++) { document.write(list[i] + " " ); } } // Driver code var N = 6; var K = 3; makeList(N, K); // This code is contributed by SoumikMondal </script> |
6 1 5 4 3 2
Time Complexity: O(N)
Auxiliary Space: O(N)