Sum of substring number

Question

What is the best solution to find the sum of the substring of a number?

For example, Sum (123) = 1 + 2 + 3 + 12 + 23 + 123 = 164.

I think this 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 1

Notice, that:

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

Here is my C # implementation, although this should be trivial for the Java port:

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 this is effective O (n).

Answer 2

~ N ^ 2 n. , :

S (s0, s1, s2,..., sn).

S = ​​< 1,2,3 > 111 * 1 + 22 * ​​2 + 3 * 3 = 164

, , N 10 .

Answer 3

@Gabe, :

A0 = 1,
A1 = A0*10 + 1,
...
An-1 = An-2 * 10 + 1,

A0-An O (n)

a[0] = 1;
for (int i=1;i<n;i++)
 a[i] = a[i - 1] * 10 + 1;

b [i]:

b[0] = a[0] * n
b[1] = a[1] * (n-1)
...

b [i] ​​O (n)

[ ]

for (int i=0;i<n;i++)
   sum += S[n-i - 1] * b[i]

Answer 4

. . , , , , . , , MOD , , 1000000007. , , , . , . .

• Modular_exp() - , a ^ b% c
• 9, 111111112, modular_exp(), .
• len - , '0' '9';

:

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 );

.

Answer 5

FWIW N

N + N-1 + N-2... 1

( ) http://en.wikipedia.org/wiki/Triangular_number

N ^ 2 + N/2

,

Answer 6

, , .

, 19,

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

If the number is 486, then the 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

Thus, in the general case, if a number is represented as a string of digits "XY", then the sum of the substrings will contain this number, which 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 a 9-digit amount

(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