Given two positive integers K and N, the task is to find the permutation present at the middle of all permutations of at most length N, consisting of integers from the range [1, K], arranged lexicographically.
Examples:
Input: K = 3, N = 2
Output: 2 1
Explanation: Lexicographical order of all possible permutations are:
- {1}.
- {1, 1}
- {1, 2}
- {1, 3}
- {2}
- {2, 1}
- {2, 2}
- {2, 3}
- {3}
- {3, 1}
- {3, 2}
- {3, 3}
Therefore, the middle lexicographically the smallest sequence is (N/2)th(= 6th) sequence, which is {2, 1}.
Input: K = 2, N = 4
Output: 1 2 2 2
Naive Approach: The simplest approach to solve the given problem is to generate all possible subsequences of a length [1, N], consisting of integers from [1, K]. Store these elements in an array. After generating all the subsequences, sort the stored list of subsequences and print the middle element of the list.
Time Complexity: O(NK)
Auxiliary Space: O(NK)
Efficient Approach: The above approach can be optimized by checking the parity of K whether K is odd or even and then find the middle lexicographically the smallest sequence accordingly. Follow the steps below to solve the problem:
- If the value of K is even, then exactly half of the sequences start with an integer K/2 or less. Therefore, the resultant sequence is K/2 followed by (N – 1) occurrence of K.
- If the value K is odd, then consider B to be a sequence that contains N occurrences of (K + 1)/2.
- For a sequence X, let f(X) be a sequence such that Xi in X is replaced with (K + 1 ? Xi).
- The only exception happens for prefixes of B.
- Start with the sequence B, and perform the following steps (N – 1)/2 times:
- If the last element of the current sequence is 1, then remove it.
- Otherwise, decrement the last element by 1, and while the sequence contains less than N elements, and insert K at the end of sequence B.
- After completing the above steps, print the sequence obtained in the array B[].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function that finds the middle the// lexicographical smallest sequencevoid lexiMiddleSmallest(int K, int N){ // If K is even if (K % 2 == 0) { // First element is K/2 cout << K / 2 << " "; // Remaining elements of the // sequence are all integer K for (int i = 0; i < N - 1; ++i) { cout << K << " "; } cout << "\n"; exit(0); } // Stores the sequence when K // is odd vector<int> a(N, (K + 1) / 2); // Iterate over the range [0, N/2] for (int i = 0; i < N / 2; ++i) { // Check if the sequence ends // with in 1 or not if (a.back() == 1) { // Remove the sequence // ending in 1 a.pop_back(); } // If it doesn't end in 1 else { // Decrement by 1 --a.back(); // Insert K to the sequence // till its size is N while ((int)a.size() < N) { a.push_back(K); } } } // Print the sequence stored // in the vector for (auto i : a) { cout << i << " "; } cout << "\n";}// Driver Codeint main(){ int K = 2, N = 4; lexiMiddleSmallest(K, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function that finds the middle the // lexicographical smallest sequence static void lexiMiddleSmallest(int K, int N) { // If K is even if (K % 2 == 0) { // First element is K/2 System.out.print(K / 2 + " "); // Remaining elements of the // sequence are all integer K for (int i = 0; i < N - 1; ++i) { System.out.print(K + " "); } System.out.println(); return; } // Stores the sequence when K // is odd ArrayList<Integer> a = new ArrayList<Integer>(); // Iterate over the range [0, N/2] for (int i = 0; i < N / 2; ++i) { // Check if the sequence ends // with in 1 or not if (a.get(a.size() - 1) == 1) { // Remove the sequence // ending in 1 a.remove(a.size() - 1); } // If it doesn't end in 1 else { // Decrement by 1 int t = a.get(a.size() - 1) - 1; a.set(a.get(a.size() - 1), t); // Insert K to the sequence // till its size is N while (a.size() < N) { a.add(K); } } } // Print the sequence stored // in the vector for (int i : a) { System.out.print(i + " "); } System.out.println(); } // Driver Code public static void main(String[] args) { int K = 2, N = 4; lexiMiddleSmallest(K, N); }}// This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach# Function that finds the middle the# lexicographical smallest sequencedef lexiMiddleSmallest(K, N): # If K is even if (K % 2 == 0): # First element is K/2 print(K // 2,end=" ") # Remaining elements of the # sequence are all integer K for i in range(N - 1): print(K, end = " ") print() return # Stores the sequence when K # is odd a = [(K + 1) // 2]*(N) # Iterate over the range [0, N/2] for i in range(N//2): # Check if the sequence ends # with in 1 or not if (a[-1] == 1): # Remove the sequence # ending in 1 del a[-1] # If it doesn't end in 1 else: # Decrement by 1 a[-1] -= 1 # Insert K to the sequence # till its size is N while (len(a) < N): a.append(K) # Print sequence stored # in the vector for i in a: print(i, end = " ") print()# Driver Codeif __name__ == '__main__': K, N = 2, 4 lexiMiddleSmallest(K, N)# This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function that finds the middle the // lexicographical smallest sequence static void lexiMiddleSmallest(int K, int N) { // If K is even if (K % 2 == 0) { // First element is K/2 Console.Write(K / 2 + " "); // Remaining elements of the // sequence are all integer K for (int i = 0; i < N - 1; ++i) { Console.Write(K + " "); } Console.WriteLine(); return; } // Stores the sequence when K // is odd List<int> a = new List<int>(); // Iterate over the range [0, N/2] for (int i = 0; i < N / 2; ++i) { // Check if the sequence ends // with in 1 or not if (a[a.Count - 1] == 1) { // Remove the sequence // ending in 1 a.Remove(a.Count - 1); } // If it doesn't end in 1 else { // Decrement by 1 a[a.Count - 1] -= 1; // Insert K to the sequence // till its size is N while ((int)a.Count < N) { a.Add(K); } } } // Print the sequence stored // in the vector foreach(int i in a) { Console.Write(i + " "); } Console.WriteLine(); } // Driver Code public static void Main() { int K = 2, N = 4; lexiMiddleSmallest(K, N); }}// This code is contributed by ukasp. |
Javascript
<script>// javascript program for the above approach // Function that finds the middle the // lexicographical smallest sequence function lexiMiddleSmallest(K, N) { // If K is even if (K % 2 == 0) { // First element is K/2 document.write(K / 2 + " "); // Remaining elements of the // sequence are all integer K for (let i = 0; i < N - 1; ++i) { document.write(K + " "); } document.write("<br/>"); return; } // Stores the sequence when K // is odd let a = []; // Iterate over the range [0, N/2] for (let i = 0; i < N / 2; ++i) { // Check if the sequence ends // with in 1 or not if (a[a.length - 1] == 1) { // Remove the sequence // ending in 1 a.pop(a.length - 1); } // If it doesn't end in 1 else { // Decrement by 1 a[a.length - 1] -= 1; // Insert K to the sequence // till its size is N while (a.length < N) { a.push(K); } } } // Print the sequence stored // in the vector for(let i in a) { document.write(i + " "); } document.write("<br/>"); }// Driver Code let K = 2, N = 4; lexiMiddleSmallest(K, N); </script> |
Output:
1 2 2 2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
