Question: What is the optimal solution to find the sum of substring of a number ?

For example, Sum (123) = 1 + 2 + 3 + 12 + 23 + 123 = 164. 

I think it is O(n^2). because 

```
sum = 0
for i in number: // O(n)
    sum += startwith(i) // O(n)
return sum

```

Any optimal solution? What is the best approach?

Here is my solution but O(n^2):

```
public static int sumOfSubstring(int i) {
  int sum = 0;

  String s = Integer.toString(i);

  for (int j = 0, bound = s.length(); j < bound; j++) {
   for (int k = j; k < bound; k++) {
    String subString = s.subSequence(j, k + 1).toString();
    sum += Integer.valueOf(subString);
   }
  }

  return sum;
 }

```

Answer: 
As @Gabe offered you can do:

```
A0 = 1,
A1 = A0*10 + 1,
...
An-1 = An-2 * 10 + 1,

```

you can compute A0-An in O(n)

```
a[0] = 1;
for (int i=1;i<n;i++)
 a[i] = a[i - 1] * 10 + 1;

```

now compute b[i]:

```
b[0] = a[0] * n
b[1] = a[1] * (n-1)
...

```

you can compute all b[i] in O(n)

Now the some is 
[Pseudo code]

```
for (int i=0;i<n;i++)
   sum += S[n-i - 1] * b[i]

```
FWIW the number of integers to add for number of N digits appears to be

N + N-1 + N-2 ... 1

Which is a triangular number (additive equivalent of a factorial)
<http://en.wikipedia.org/wiki/Triangular_number>

The number of additions
N^2 + N / 2

However, this doesn't consider the work needed to split out the digits