For example, if n=14, the output should be 10; n=22, the output should be 30=10+20; n=102, output=(10+...+100)+101+102=5703In this problem, n is smaller than $10^{18}$ , and the algorithm should finish within 1 second.
The sum of all integers less than n with a zero
algorithms
Let $S(m)$ be the sum of all numbers with at most $m$ digit, i.e $S(m)=10^{m+1}\cdot (10^{m+1} - 1) / 2$.Let $C(m)$ be the number of at most m digit numbers which contains $0$.Let $F(m)$ be the sum of numbers with zero in them such that they have at most $m$ digits.Then is easy to find a recursive relation for $C(m)$ (hint: what is its dual?), after that you can find a recursive relation between $C(m),F(m),S(m)$ as follow:The main problem is finding $F(m)$, but we know that, new number of m digit with zero in it, is created by number of $m-1$ digit with zero in it and padded by the numbers $0...9$, or $m-1$ digit numbers without zero padded with new zero to the end, or $m-1$ digit numbers with zero in them:$F(m) = [F(m-1) \cdot 10 + C(m-1) \cdot 45] + (S(m-1) - F(m-1))\cdot 10 +F(m-1)\Rightarrow$$F(m) = F(m-1)+S(m-1)\cdot 10+C(m-1)\cdot 45$Now for calculating upto specific number, first you need to find the number of its digit, then, write it as sum of power of 10, then you can find each possible sum to each digit (from right to left).For such a small range this works much less than a second (because is $O(\log n)$), anyway you can preprocess it.