I've got some expression
$\sum_{i=1}^n\left( 2^{i-1} a_i \sum_{k=0}^{n-i}10^k \binom{n-i}{k} \right)$
$a_i$ stands for i-th digits in number. I came up with this formula from task in which we had to delete some set of digits from given number and then sum those numbers
so for example we have number 123 then possible numbers we can get are: $ 1 + 2 + 3 + 12 + 13 + 23 + 123 $
I won't really explain why this formula works, but computing it it will give $O(n^2)$ time. Can we compress it somehow to get $O(n)$ ? I'm mostly interested in second sum.
Cheers,
Chris