1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.