# Permutation present at the middle of lexicographic ordering of permutations of at most length N made up integers up to K

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 = 2Output:2 1Explanation: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}(= 6^{th}) sequence, which is {2, 1}.

Input:K = 2, N = 4Output: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(N^{K})**Auxiliary Space:** O(N^{K})

**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**X**in_{i}**X**is replaced with**(K + 1 − X**._{i}) - The only exception happens for prefixes of
**B**.

- For a sequence
- 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**.

- If the last element of the current sequence is
- 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 sequence` `void` `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 Code` `int` `main()` `{` ` ` `int` `K = 2, N = 4;` ` ` `lexiMiddleSmallest(K, N);` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `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 sequence` `def` `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)` ` ` `# Prthe sequence stored` ` ` `# in the vector` ` ` `for` `i ` `in` `a:` ` ` `print` `(i, end ` `=` `" "` `)` ` ` `print` `()` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `K, N ` `=` `2` `, ` `4` ` ` `lexiMiddleSmallest(K, N)` `# This code is contributed by mohit kumar 29.` |

## C#

`// C# program for the above approach` `using` `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)

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. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.