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: 
All the above answers looks great. I was recently solving a similar problem. The formula presented above works well but as you can see as the length of the string increases the computation becomes difficult and the solution really large. Usually when the length of the string is really large you will be asked to give the answer after MOD a large number say 1000000007. So now you can easily compute the values using little bit of modular Arithmetic, or to be specific [Modular exponentiation](http://en.wikipedia.org/wiki/Modular_exponentiation/) and [Multiplicative inverse](http://en.wikipedia.org/wiki/Modular_multiplicative_inverse). So the new formula after modification for large inputs can be written as.
**Assumption made.**

* Modular\_exp() is the function that computes the value of a^b % c
* multiplicative inverse variable is the multiplicative inverse of 9 which is 111111112, which can be found out using the same modular\_exp() function, but here I just hard coded it.
* len is the total length of the string that has only characters from '0' to '9';

Here is the code:

```
FOR(i, len) {
    coef = (( ( modular_exp(10, len - i, MOD) - 1) * multiinverse ) % MOD) * (i + 1) % MOD;
    res += ( coef * (s[i] - '0') ) % MOD;
}
printf("%lld\n", res % MOD );

```

That's it.
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