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: 
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.
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