Generate a permutation of first N natural numbers having count of unique adjacent differences equal to K

Shreya Deep
Last Updated: May 13, 2022

Introduction

A permutation of first n natural numbers is an array of numbers from 1 to n, arranged in any order that no number appears twice in the array. 

In this article, we will learn how to generate a permutation of first n natural numbers in which the number of unique differences between adjacent numbers is equal to k.

Problem Statement

Given the value of n and k, find a permutation of first n natural numbers such that the number of unique differences between adjacent numbers is equal to k.

For example:

Input

n =5,k=3


Output

a[] = 1 5 2 3 4


Explanation:

The difference between a[1] and a[0] = 4.
The difference between a[2] and a[1] = 3.
The difference between a[3] and a[2] = 1.
The difference between a[4] and a[3] = 1.
Thus, the values of differences are 4,3 and 1. The total count of unique differences is three, which is what we need.

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;
}


Output

1 5 2 3 4


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;
}


Output

1 5 2 3 4


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;
}


Output

1 5 2 3 4


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).

Frequently asked questions

  1. What are queues in data structure?
    A queue is a linear data structure that follows the FIFO (first in, first out) property.
     
  2. 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.
     
  3. 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.

Key Takeaways

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 on two pointer approach are maximum distanceninja and sorted arrayssmallest subarray with k distinct elementsvalid stringthe leftmost column with at least a oneminimum subarray with the required sum, and some of the problems on deque are deque and stack using deque

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on CodeStudio now!

Happy Coding!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think