сумма подстроки числа

Question

Какое оптимальное решение найти сумму подстроки числа?

Например, Sum (123) = 1 + 2 + 3 + 12 + 23 + 123 = 164.

Я думаю, что это O (n ^ 2).потому что

sum = 0
for i in number: // O(n)
    sum += startwith(i) // O(n)
return sum

Есть ли оптимальное решение?Каков наилучший подход?

Вот мое решение, но 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

Обратите внимание:

• Для числа XY у вас есть 11X + 2Y.
• Для числа XYZ у вас есть 111X + 22Y + 3Z.
• ДляWXYZ, у вас 1111W + 222X + 33Y + 4Z.

Вот моя реализация C #, хотя она должна быть тривиальной для переноса на 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;
}

Обратите внимание, что это эффективноО (п).

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

Все вышеприведенные ответы выглядят великолепно. Недавно я решал похожую проблему. Формула, представленная выше, работает хорошо, но, как вы можете видеть, когда длина строки увеличивается, вычисление становится трудным, а решение действительно большим. Обычно, когда длина строки действительно велика, вас попросят дать ответ после 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 4

Как предложил @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 5

Не новый ответ, а уточнение принятого ответа, данного Гейбом.

Скажите, что число равно 19, тогда сумма равна

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

Если число равно 486, то сумма равна

* 1007.*

Таким образом, в общем случае, если число представлено в виде строки цифр "XY", то сумма подстрок будет означать, что число может быть вычислено как

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

Для числа из 9 цифр сумма равна

(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

Answer 6

FWIW число целых чисел, которое нужно добавить для числа N цифр, выглядит как

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

Какое треугольное число (аддитивный эквивалент факториала) http://en.wikipedia.org/wiki/Triangular_number

Количество дополнений N ^ 2 + N / 2

Однако это не учитывает работу, необходимую для выделения цифр