Generate a permutation of first N natural numbers having count of unique adjacent differences equal to K | Set 2
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 are 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
The naive approach and the two-pointer approach of this problem are already discussed here. This article discusses a different approach deque.
Approach: It is easy to see that, answers for all values of K between [1, N-1] can be generated. For any K outside this range, there exists no answer. To solve the problem maintain a double-ended queue for all the current elements and a vector to store the sequence. Also, maintain a boolean value that will help to determine to pop the front or back element. Iterate the remaining element and if K is greater than 1 then push the element according to the boolean value and decrease K by 1. Flip the boolean value so that all remaining differences will have value 1. Follow the steps below to solve the problem:
- If K is greater than equal to N or less than 1, then print -1 and return as no such sequence exists.
- Initialize a deque dq[] to maintain the order of elements.
- Iterate over the range [2, N] using the variable i and push i into the back of deque dq[].
- Initialize a boolean variable front as true.
- Initialize a vector ans[] to store the answer and push 1 into the vector ans[].
- If K is greater than 1, then subtract 1 from K and xor the value of front with 1.
- Iterate over the range [2, N] using the variable i and check:
- If the front is 1, then pop the front of the deque dq[] and push it in the vector ans[] otherwise, pop the back of the deque dq[] and push it in the vector ans[]. Also, if K is greater then, then subtract 1 from K and xor the value of front with 1.
- Traverse the array ans[] and print its elements.
Below is the implementation of the above approach.
C++
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; // Function to calculate the required array void K_ValuesArray( int N, int K) { // Check for base cases if (K < 1 || K >= N) { cout << -1; return ; } // Maintain a deque to store the // elements from [1, N]; deque< int > dq; for ( int i = 2; i <= N; i++) { dq.push_back(i); } // Maintain a boolean value which will // tell from where to pop the element bool front = true ; // Create a vector to store the answer vector< int > ans; // Push 1 in the answer initially ans.push_back(1); // Push the remaining elements if (K > 1) { front ^= 1; K--; } // Iterate over the range for ( int i = 2; i <= N; i++) { if (front) { int val = dq.front(); dq.pop_front(); // Push this value in // the ans vector ans.push_back(val); if (K > 1) { K--; // Flip the boolean // value front ^= 1; } } else { int val = dq.back(); dq.pop_back(); // Push value in ans vector ans.push_back(val); if (K > 1) { K--; // Flip boolean value front ^= 1; } } } // Print Answer for ( int i = 0; i < N; i++) { cout << ans[i] << " " ; } } // Driver Code int main() { int N = 7, K = 1; K_ValuesArray(N, K); return 0; } |
Java
// Java Program for the above approach import java.util.*; class GFG{ // Function to calculate the required array static void K_ValuesArray( int N, int K) { // Check for base cases if (K < 1 || K >= N) { System.out.print(- 1 ); return ; } // Maintain a deque to store the // elements from [1, N]; Deque<Integer> dq = new LinkedList<Integer>(); for ( int i = 2 ; i <= N; i++) { dq.add(i); } // Maintain a boolean value which will // tell from where to pop the element boolean front = true ; // Create a vector to store the answer Vector<Integer> ans = new Vector<Integer>(); // Push 1 in the answer initially ans.add( 1 ); // Push the remaining elements if (K > 1 ) { front ^= true ; K--; } // Iterate over the range for ( int i = 2 ; i <= N; i++) { if (front) { int val = dq.peek(); dq.removeFirst(); // Push this value in // the ans vector ans.add(val); if (K > 1 ) { K--; // Flip the boolean // value front ^= true ; } } else { int val = dq.getLast(); dq.removeLast(); // Push value in ans vector ans.add(val); if (K > 1 ) { K--; // Flip boolean value front ^= true ; } } } // Print Answer for ( int i = 0 ; i < N; i++) { System.out.print(ans.get(i)+ " " ); } } // Driver Code public static void main(String[] args) { int N = 7 , K = 1 ; K_ValuesArray(N, K); } } // This code is contributed by 29AjayKumar |
Python3
# python Program for the above approach from collections import deque # Function to calculate the required array def K_ValuesArray(N, K): # Check for base cases if (K < 1 or K > = N): print ( "-1" ) return # Maintain a deque to store the # elements from [1, N]; dq = deque() for i in range ( 2 , N + 1 ): dq.append(i) # Maintain a boolean value which will # tell from where to pop the element front = True # Create a vector to store the answer ans = [] # Push 1 in the answer initially ans.append( 1 ) # Push the remaining elements if (K > 1 ): front ^ = 1 K - = 1 # Iterate over the range for i in range ( 2 , N + 1 ): if (front): val = dq.popleft() # Push this value in # the ans vector ans.append(val) if (K > 1 ): K - = 1 # Flip the boolean # value front ^ = 1 else : val = dq.pop() # Push value in ans vector ans.append(val) if (K > 1 ): K - = 1 # Flip boolean value front ^ = 1 # Print Answer for i in range ( 0 , N): print (ans[i], end = " " ) # Driver Code if __name__ = = "__main__" : N = 7 K = 1 K_ValuesArray(N, K) # This code is contributed by rakeshsahni |
C#
// C# Program for the above approach using System; using System.Collections.Generic; class GFG { // Function to calculate the required array static void K_ValuesArray( int N, int K) { // Check for base cases if (K < 1 || K >= N) { Console.Write(-1); return ; } // Maintain a deque to store the // elements from [1, N]; LinkedList< int > dq = new LinkedList< int >(); for ( int i = 2; i <= N; i++) { dq.AddLast(i); } // Maintain a boolean value which will // tell from where to pop the element bool front = true ; // Create a vector to store the answer List< int > ans = new List< int >(); // Push 1 in the answer initially ans.Add(1); // Push the remaining elements if (K > 1) { front ^= true ; K--; } // Iterate over the range for ( int i = 2; i <= N; i++) { if (front) { int val = dq.First.Value; dq.RemoveFirst(); // Push this value in // the ans vector ans.Add(val); if (K > 1) { K--; // Flip the boolean // value front ^= true ; } } else { int val = dq.Last.Value; dq.RemoveLast(); // Push value in ans vector ans.Add(val); if (K > 1) { K--; // Flip boolean value front ^= true ; } } } // Print Answer for ( int i = 0; i < N; i++) { Console.Write(ans[i] + " " ); } } // Driver Code public static void Main() { int N = 7, K = 1; K_ValuesArray(N, K); } } // This code is contributed by Saurabh Jaiswal |
Javascript
<script> // Javascript Program for the above approach // Function to calculate the required array function K_ValuesArray(N, K) { // Check for base cases if (K < 1 || K >= N) { document.write(-1); return ; } // Maintain a deque to store the // elements from [1, N]; let dq = new Array(); for (let i = 2; i <= N; i++) { dq.push(i); } // Maintain a boolean value which will // tell from where to pop the element let front = true ; // Create a vector to store the answer let ans = new Array(); // Push 1 in the answer initially ans.push(1); // Push the remaining elements if (K > 1) { front ^= true ; K--; } // Iterate over the range for (let i = 2; i <= N; i++) { if (front) { let val = dq[0]; dq.shift(); // Push this value in // the ans vector ans.push(val); if (K > 1) { K--; // Flip the boolean // value front ^= true ; } } else { let val = dq.Last.Value; dq.pop(); // Push value in ans vector ans.push(val); if (K > 1) { K--; // Flip boolean value front ^= true ; } } } // Print Answer for (let i = 0; i < N; i++) { document.write(ans[i] + " " ); } } // Driver Code let N = 7, K = 1; K_ValuesArray(N, K); // This code is contributed by Saurabh Jaiswal </script> |
1 2 3 4 5 6 7
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us