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]

```
Not a new answer but elaboration of accepted answer given by Gabe.

Say number is 19 then sum is

```
1+9+19
= 1+ 9 + (10*1+9)
= 11*1 + 2*9

```

If number is 486 then sum is

```
= 4 + 8 + 6 + 48+ 86 +486
= 4 + 8 + 6 + (10*4+8) + (10*8+6) + (100*4+10*8+6)
= 111*4+22*8+3*6

```

So in general term if a number is represented as a string of digits "XY" then sum of sub-strings will bw that number can be calculated as 

```
sum of XY  = X +Y + (10X+Y) 
= 11X+2Y

sum of XYZ = X + Y + Z + (10X + Y)+ (10 Y+ Z) + (100X+ 10Y+Z)
= 111X+22Y+3Z

sum of XYZW = x+ y+ z + w + (10x + y) + (10y+ z)+ (10z+ w)+(100X+ 10Y+Z)+(100y+ 10z+w)+(1000x+100y+10z+w)
=1111x+222y+33z+4w

```

For 9 digit number sum is 

```
(9 times 1)*1st + (8 times 2)*2nd+ (7 times 3)*3rd + (6 times 4)*4th+(5 times 5)*5th +(4 times 6)*6th  +(3 times 7)*7th+(3 times 8)*8th+(3 times 9)*9th

```