sum of substring of a number

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).toStri开发者_运维技巧ng();
    sum += Integer.valueOf(subString);
   }
  }

  return sum;
 }

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:

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.

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]

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 and 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

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