Lexicographic permutation

Question

Consider that you have a permutation of $n$ elements from $1$ to $n$ and you need to sort the elements lexicographical . for example sorted permutation for $n=11$ is $1,10,11,2,3,4,5,6,7,8,9$ .Now consider this notation $Q(n,k)$ as position of number $k$ in lexicographical sorted permutation. $Q(11,2)=4$. We are given $k$ and $m$ we need to find minimum $n$ such that $Q(n,k)=m$ holds.

I could only find that $n>=max(m,k)$ and for next i do not know how to solve it .

Source of question link

Answer 1

First, there is one special case of $k$, the powers of 10, which are 1, 10, 100, etc. Their positions at a lexicographically ordered sequence of positive integers are fixed.

• 1 is always at the 1st position.
• 10 is always at the 2nd position once it appears. Any number except 1 and itself will be sorted after it.
• 100 is always at the 3rd position once it appears. Any number except 1, 10 and itself will be sorted after it.
• And so on.

We should process this peculiar case first.

The position of $k$ in the lexicographically sorted sequence is determined by the numbers that are before $k$ (lexicographically). These numbers fall into three categories.

• the numbers that are smaller than $k$. If a permutation of 1, 2, ..., $n$ contains $k$, it must contain all these numbers as well.
• $k$ itself.
• the numbers that are bigger than $k$.

Let us compute how many numbers before $k$ are smaller than $k$. For example, take k $=$ 619. Any number smaller than $k$ has at most three digits.

• All three-digit numbers before 619 constitute the interval [100, 619).
• All two-digit numbers before 619 constitute the interval [10, 61].
• All one-digit numbers before 619 constitute the interval [1, 6].

In total, there are 519 + 52 + 6 $=$ 577 numbers that are smaller than 619 and before 619. So if $m\le$ 577 + 1, where 1 stands for 619 itself, no $n$ can satisfy $Q(n,\,$619$)=m$. If $m=$ 578, the minimum $n$ is 619 itself.

Otherwise, the given $m$ is bigger than 1 plus the number of numbers smaller than $k$ and before $k$. We have to include numbers bigger than $k$ that are before $k$ to increase the position of $k$. For the same example, when $m\gt 578$, $n=$ 619 is not enough.

• Try adding the number between 1000 inclusive and 6190 exclusive.
• If that is not enough, try adding the number between 10000 inclusive and 61900 exclusive.
• If that is not enough, try adding the number between 100000 inclusive and 618900 exclusive.
• And so on.

---