Kth element in permutation of first N natural numbers having all even numbers placed before odd numbers in increasing order

Kth element in permutation of first N natural numbers having all even numbers placed before odd numbers in increasing order

Given two integers N and K, the task is to find the K^th element in the permutation of first N natural numbers arranged such that all the even numbers appear before the odd numbers in increasing order.

Examples :

Input: N = 10, K = 3  
Output: 6
Explanation:
The required permutation is {2, 4, 6, 8, 10, 1, 3, 5, 7, 9}.
The 3^rd number in the permutation is 6.

Input: N = 5, K = 4
Output: 3
Explanation:
The required permutation is {2, 4, 1, 3, 5}.
The 4^th number in the permutation is 3.

Naive Approach: The simplest approach to solve the problem is to generate the required permutation of first N natural numbers and then traverse the permutation to find the K^th element present in it.
Follow the steps below to solve the problem:

• Initialize an array, say V[] of size N., to store the required sequence.
• Insert all even numbers less than or equal to N into V[].
• Then, insert all odd numbers less than or equal to N into V[].
• After forming the array, print the value of V[K – 1] as the result.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void findKthElement(int N, int K) {          vector<int> v;                  for (int i = 1; i <= N; i++) {         if (i % 2 == 0) {             v.push_back(i);         }     }                  for (int i = 1; i <= N; i++) {         if (i % 2 != 0) {             v.push_back(i);         }     }             cout << v[K - 1]; }    int main() {     int N = 10, K = 3;     findKthElement(N, K);        return 0; }

Time Complexity: O(N)
Auxiliary Space: O(N)

Efficient Approach: To optimize the above approach, the idea is based on the observation that the first N / 2 elements are even and the value of the K^th element in the first half is equal to K * 2. If K > N/2, the value of the K^th element, depends on whether N is odd or even. 
Follow the steps below to solve the problem:

• Initialize a variable, say ans, to store the K^th element.
• Check if the value of K ≤ N/2. If found to be true, update ans to K*2.
• Otherwise, K lies in the second half. In this case, ans depends on the value of N.
• Print the value of ans as the result.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void findKthElement(int N, int K) {          int ans = 0;                  if (K <= N / 2) {         ans = K * 2;     }             else {                     if (N % 2 == 0) {             ans = (K * 2) - N - 1;         }                     else {             ans = (K * 2) - N;         }     }             cout << ans; }    int main() {     int N = 10, K = 3;     findKthElement(N, K);        return 0; }

Time Complexity: O(1)
Auxiliary Space: O(1)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)