### himanshu1212's blog

By himanshu1212, history, 9 months ago,

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

 » 9 months ago, # |   0 Auto comment: topic has been updated by himanshu1212 (previous revision, new revision, compare).
 » 9 months ago, # |   +22 i am unable to understand this question can u give some more details to problem.
 » 9 months ago, # | ← 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. Spoilerint solve(int prev, int n) { if(prev > n) return 0; int ans = 1; int d = prev%10; for(int i=d;i<=9;i++) ans += solve(prev*10+i,n); return ans; } int32_t main() { int n; cin >> n; int ans = 0; for(int i=1;i<=9;i++) ans += solve(i,n); cout << ans << '\n'; return 0; } 
•  » » 9 months ago, # ^ |   0 Would it perform well on values of N up to 10^17?
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Yes I checked, it's running within 1 sec.
•  » » » » 6 weeks ago, # ^ |   0 bro, this also shows TLE
•  » » » » » 6 weeks ago, # ^ |   +2 sad life
•  » » » » » 6 weeks ago, # ^ |   0 I ran it in CF custom invocation and this is the vedict for n = 1e17 3124549 ===== Used: 15 ms, 0 KB 
 » 9 months ago, # | ← 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.
•  » » 9 months ago, # ^ |   0 Path-counting on a grid is so powerful...
 » 6 weeks ago, # |   0 bro if you solved this then provide me approach of this problem which dont show TLE