himanshu1212's blog

By himanshu1212, history, 3 years ago, In English

We have to count the numbers up to N(N can be up to 10^17) such that the digits from the smallest possible permutation for example if I take N=13 then the answer would be 12 since 10 is not the smallest permutation of the digits '0' and '1'.

  • Vote: I like it
  • -4
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

i am unable to understand this question can u give some more details to problem.

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

This problem can be easily solved using recursion, assume the current number is n and its the smallest permutation, and the last digit is d, then any digit we append in the last must be greater than or equal to d. It's very easy to understand but still if you have any doubt please reply.

Spoiler
»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

We can view this question as the typical problem of counting the number of paths on a grid. Going to the right can be seen as choosing the next digit equal to the previous digit and going up $$$x$$$ cells on the grid represents that the next digit is equal to the previous plus $$$x$$$. The answer will be the total number of ways to reach the right part of the grid (at any height), notice that every path represents a different number whose digits are in non-decreasing order.

Let $$$k$$$ be the largest non-negative number such that $$$10^{k} \leq n$$$, then $$$n$$$ has $$$k + 1$$$ digits. First, we count the number of numbers with the desired property that are less than $$$10^{k}$$$, which for the previous analysis we can represent as the number of different paths on a grid of size $$$10 \times k$$$ (there are $$$k$$$ digits with values between $$$0$$$ and $$$9$$$), also we have to subtract the path representating $$$0$$$.

Then, the answer for that is equal to $$$\binom{k}{0} + \binom{k + 1}{1} + \binom{k + 2}{2} + \dots + \binom{k + 9}{9} - 1 = \binom{k + 10}{9} - 1$$$. If the most significant digit of $$$n$$$ is $$$a_{k + 1}$$$ we add the number of different paths to travel a grid of size $$$(a_{k + 1} - 1) \times (k + 1)$$$ (since the first digit could be anything between $$$1$$$ and $$$a_{k + 1} - 1$$$, note that including numbers with most significant digit equal to $$$a_{k + 1}$$$ would result in a overcount) to the previous result. We continue this way until the digits of $$$n$$$ are not in non-decreasing order (because after this point there won't be more numbers satisfying the conditions), for example if the $$$(k + 2 - i)$$$-th, $$$i \neq k + 1$$$, most significant digit of $$$n$$$ is $$$a_{i}$$$ we add to the answer the number of paths in a $$$(a_{i} - a_{i + 1}) \times i$$$ grid.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Path-counting on a grid is so powerful...