Solution Approach
Approach 1: Naive approach
The most basic approach to follow is to take an array fill it with elements from 1 to n in ascending order and then keep reversing the subarrays arr[0,n-1], arr[1,n-1], arr[2,n-1],...., arr[k-1,n-1].
In this way, what will happen is, we will be able to create an array like this: [1, n-1, 2, n-2,..., and after a certain point when we stop reversing, the further elements will be consecutive so that the absolute difference will be one further.
Thus, this solution works because we are creating k-1 different absolute differences when we are reversing.
At the point we stopped reversing, the absolute difference was one further.
Hence, the total number of absolute differences is k.
Steps of implementation are:
-
In the function make_permutation():
-
Create an array of size n and fill numbers from 1 to n in this array in ascending order.
-
Reverse the array k times from position i to n-1 where i varies from 0 to k-1.
- Print the array.
C++ implementation
#include <bits/stdc++.h>
using namespace std;
// Function to reverse an array
void reverse(int ans[], int s, int e){
// Iterate until s < e
while (s < e){
// Swap
int temp = ans[s];
ans[s] = ans[e];
ans[e] = temp;
s++;
e--;
}
}
void make_permutation(int n, int k){
//Create an array of size n and fill numbers from 1 to n in this array in ascending order.
int ans[n];
for(int i = 1; i <= n; i++){
ans[i-1] = i;
}
// Reverse the array k times from position i to n-1 where i varies from 0 to k-1.
for(int i = 1; i < k; i++){
reverse(ans, i, n - 1);
}
// Print the answer array
for(int i = 0; i < n; i++){
cout << ans[i] << " ";
}
cout<<endl;
}
// Driver code
int main()
{
// Input the values
int n = 5, k = 3;
// Call the function make_permutation
make_permutation(n, k);
return 0;
}
You can also try this code with Online C++ Compiler
Output
1 5 2 3 4
You can also try this code with Online C++ Compiler
Complexities
Time complexity
O(n*k), where n and k are the given inputs
Reason: Initially, we’re filling the array with n elements which take O(n) time. Then, we’re reversing the array k-1 times. Each reversal takes O(n) time. Thus, the total time for reversing k-1 times is O(n*k). Therefore, the total time complexity is O(n+n*k) equal to O(n*k).
Space complexity
O(n), where n is the given value in the input
Reason: Only space taken is the space taken by the array which contains the permutation. Thus, the total space complexity is O(n).
Approach 2: Two pointer approach
One way to optimize the above solution is to solve this problem using two pointers.
You can observe that numbers from 1,2,3 and so on are getting added in the array alternatively with numbers like n-1,n-2,n-3,.., in between them.
And this is happening until we get k unique differences.
Note that, when we add one initially, then n-1, we create an absolute difference of n-1-1 = n-2.
Then, if we add two into the array, we create another absolute difference which is n-1-2 = n-3.
Thus, each time we add a number in this (i.e., one from the beginning, one from the end), we’re creating a new type of absolute difference.
Therefore, each time we add a number in this way, we can decrease the value of k by 1.
And when k==1, we stop adding numbers in this way and add consecutive numbers then so that the difference will then make the total different differences equal to k.
Steps of implementation are:
-
In the function make_permutation():
-
Declare and initialize two variables called l and r as l=1 and r=n. Here, l and r denote the respective end of numbers arranged in ascending order from 1 to n.
-
Initialize a vector called “arr,” which will store the answer and in which we will insert numbers.
-
Initialize another variable called current_k as current_k = k. This will denote the current value of k left.
-
Declare and initialize a variable last as last =0. It has the value 0 if we need to add the value l and one if we need to add the value r.
-
Push the number 1 into the answer vector, change the value of l to 2, and change the value of the variable last to 1.
-
Now, while(k!=1), keep pushing numbers l and r in the vector alternatively and keep decreasing the value of r and increasing the value of l. We keep decrementing k each time. For checking whether to add l or r value, we check the variable last, which has the value 0 if we need to add the value l and one if we need to add the value r. Initially, we keep the value of last as 0 since we need to put one first.
-
Now, after the while loop, if the last value you entered was from l, i.e., last==1, insert all the values from l to r in the vector. Otherwise, if the last value entered was from r, i.e., last==0, insert all the values from r to l in the vector.
- Print the vector.
C++ implementation
#include <bits/stdc++.h>
using namespace std;
void make_permutation(int n, int k){
//Declare and initialize two variables called l and r as l=1 and r=n
int l = 1;
int r = n;
/*
Initialize a vector called "arr" which will store the answer and in
which we will insert numbers.
*/
vector<int>ans;
/*
Initialize another variable called current_k as current_k = k.
This will denote the current value of k left.
*/
int current_k = k;
/*
Declare and initialize a variable last as last =0. It has the value
0 if we need to add the value l and 1 if we need to add the value r.
*/
int last = 0;
/*
Push the number 1 into the answer vector, change the value of l to 2,
and change the value of the variable last to 1.
*/
ans.push_back(1);
l++;
last = 1;
/*
while(k!=1), keep pushing numbers l and r in the vector alternatively
and also keep decreasing the value of r and increasing the value of l.
We keep decrementing k each time.
*/
while(k!=1){
if(last==0){
ans.push_back(l);
l++;
k--;
last = 1;
}
else{
ans.push_back(r);
r--;
k--;
last = 0;
}
}
/*
if the last value you entered was from l, i.e, last==1, insert all
the values from l to r in the vector. Otherwise, if the last value
entered was from r, i.e, last==0, insert all the values from r to l
in the vector.
*/
if(last==1){
for(int i=l;i<=r;i++){
ans.push_back(i);
}
}
else{
for(int i=r;i>=l;i--){
ans.push_back(i);
}
}
//Print the vector
for(int i=0;i<n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
// Driver code
int main()
{
// Input the values
int n = 5, k = 3;
// Call the function make_permutation
make_permutation(n, k);
return 0;
}
You can also try this code with Online C++ Compiler
Output
1 5 2 3 4
You can also try this code with Online C++ Compiler
Complexities
Time complexity
O(n), where n is the value given in the input.
Reason: Here, the while(k!=1) loop is running for k-1 times and then for n-k+1 times. Thus, the total time complexity is O(k-1+n-k+1) = O(n).
Space complexity
O(n), where n is the given value in the input
Reason: Only space taken is the space taken by the vector which contains the permutation. Thus, the total space complexity is O(n).
Approach 3: Using queues
Another approach is quite similar to the last one, but the only difference is that we are using another data structure here, which is a deque.
So, what we will do is, we will create a deque in which we store the elements from 1 to n. Then, we keep a variable “front,” which has the value 1, if we need to pop the front element from the deque and push it into our answer vector; otherwise, 0, if we need to pop the back element from the deque and push it into our answer vector.
We do this in a loop that runs n times. Also, in each iteration, we need to decrement the value of k.
In the iteration in which, k<=1, we need to stop changing the value of front as we want to keep pushing the consecutive elements now (i.e., if we pushed the last element from the front, we want to push elements from the front only now as they will all have the absolute difference of 1 and vice versa).
Steps of implementation are:
-
In the function make_permutation():
-
Declare a deque called dq, and push all the elements from 1 to n into it.
-
Declare and initialize a variable front, which has the value one initially.
-
Declare a vector “ans,” which will store the answer.
-
Push the value one into the answer vector and pop out one from the front of the deque. Also, change the value of the front to 0.
-
Now, keep pushing numbers into the ans vector. Run a loop from 2 to n, decide which value to push, and check the front value. If front==1, push the front value of the deque; otherwise, push the back value from the deque. After pushing, decrement the value of k and change the front value from 0 to 1 or 1 to 0.
If k<=1, we don’t change the front value further as we need to keep pushing the elements from the same end from now onwards.
- Print the answer vector.
C++ implementation
#include <bits/stdc++.h>
using namespace std;
void make_permutation(int n, int k){
//Declare a deque called dq, and push all the elements from 1 to n into it.
deque<int>dq;
for(int i=1;i<=n;i++){
dq.push_back(i);
}
//Declare and initialize a variable front, which has the value 1 initially
int front = 1;
//Declare a vector "ans", which will store the answer
vector<int>ans;
/*
Push the value 1 into the answer vector and pop out 1 from the front of
the deque.
*/
ans.push_back(1);
dq.pop_front();
//change the value of front to 0.
front = 0;
/*
keep pushing numbers into the ans vector. Run a loop from 2 to n, decide
which value to push, by checking the value of front
*/
for(int i=2;i<=n;i++){
/*
If front==1, push the front value of the deque, otherwise, push
the back value from the deque
*/
if(front==1){
ans.push_back(dq.front());
dq.pop_front();
//decrement the value of k
k--;
/*
change the value of front from 0 to 1 or 1 to 0
If k is <=1, we don't change the value of front further
as we need to keep pushing the elements from the same end
from now onwards.
*/
if(k>1){
front = 0;
}
}
else{
ans.push_back(dq.back());
dq.pop_back();
//decrement the value of k
k--;
/*
change the value of front from 0 to 1 or 1 to 0
If k is <=1, we don't change the value of front further
as we need to keep pushing the elements from the same end
from now onwards.
*/
if(k>1){
front = 1;
}
}
}
//Print the answer vector
for(int i=0;i<n;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
}
// Driver code
int main()
{
// Input the values
int n = 5, k = 3;
// Call the function make_permutation
make_permutation(n, k);
return 0;
}
You can also try this code with Online C++ Compiler
Output
1 5 2 3 4
You can also try this code with Online C++ Compiler
Complexities
Time complexity
O(n), where n is the value given in the input.
Reason: We are only running two loops. One for pushing values into deque and another for building the answer. Both take O(n) time. Thus, the total time complexity is O(n).
Space complexity
O(n), where n is the given value in the input
Reason: The space is taken by deque and the answer vector. Each takes a space of O(n). Thus, the total space complexity is O(n).
Must Read C Program to Reverse a Number
Frequently Asked Questions
What are queues in data structure?
A queue is a linear data structure that follows the FIFO (first in, first out) property.
What are the different types of queues in data structure?
There are four types of queues – simple/linear Queue, Circular Queue, priority queue, and double-ended Queue.
What is a permutation of n numbers?
A permutation of n numbers is an array containing n numbers from 1 to n such that each number occurs only once.
Also Read - Strong number in c
Conclusion
In this article, we discussed the problem of finding a permutation of n numbers such that the number of different differences between adjacent numbers is equal to k. Efficient solutions to this problem required a two-pointer approach and the data structure deque. For gaining proficiency, you can practice more problems on these two topics. Some of the problems with two pointer approach are maximum distance, ninja and sorted arrays, smallest subarray with k distinct elements, valid string, the leftmost column with at least a one, minimum subarray with the required sum, and some of the problems on deque are deque and stack using deque.
More recommended Problems
Are you planning to ace the interviews with reputed product-based companies like Amazon, Google, Microsoft, and more?
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Happy Coding!
24+ registered 
