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: 
Observe that:

* For the number XY you have 11X + 2Y.
* For the number XYZ you have 111X + 22Y + 3Z.
* For WXYZ, you have 1111W + 222X + 33Y + 4Z.

Here's my C# implementation, though it should be trivial to port to Java:

```
static long SumSubtring(String s)
{
    long sum = 0, mult = 1;
    for (int i = s.Length; i > 0; i--, mult = mult * 10 + 1)
        sum += (s[i - 1] - '0') * mult * i;
    return sum;
}

```

Note that it is effectively O(n).
There are definitely ~N^2 possible substrings of a given string of length n. However, we CAN compute the sum in linear time, using the following equation:

![alt text](https://i.stack.imgur.com/dwrQr.jpg)

S stands for the sequence of digits (s0, s1, s2, ... , sn).

For S=<1,2,3> it returns 111\*1+22\*2+3\*3=164

Note that the running time is **linear** if we compute the N powers of 10 beforehand, or progressively during the loop.