Блог пользователя himanshu1212

Автор himanshu1212, история, 3 года назад, По-английски

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'.

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.