1
$\begingroup$

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

  • 0
    Oh, you are right, thank you very much!2012-10-08

2 Answers 2

1

We have by the Binomial Theorem $(1+a)^m=\sum_{k=0}^m \binom{m}{k}a^k.$ Let $m=n-i$ and $a=10$. That simplifies the inner sum.

  • 0
    Well, it is $11^{n-i}$, so there is some dependence on $i$.2012-10-08
3

The problem on digits has a linear-time evaluation by recursion on the $a_i$. The complexity is $O(n (\log n)^c)$ in bit operations, and $O(n)$ in arithmetic operations.

If $S_n$ is the sum of all numbers formed by deletions from the substring of $n$ first digits, then $S_{n+1} = S_n + (10S_n + 2^n a_{n+1})$. The recursion starts from $S_0 = 0$. This implies that $a_i$ has a coefficient of $2^{i-1}11^{n-i}$ when the sum is written as a linear function of the digits, but the recursive evaluation is faster than computing large powers of $11$ at every step. On a computer the efficiency of the sum can be optimized by starting from $2^{n-1}$ and performing "divide by 2, multiply by 11" at every step to get the coefficients, and this is about the same complexity as calculation from the recurrence.