алгоритм для нахождения суммы дальности равной размеру массива

Question

У меня есть массив A размером n натуральных чисел.Мне нужен алгоритм в O (n), который находит 2 индекса: i и j, поэтому сумма подмассива A [i ... j] будет делиться на n без остатка.

Например,: Если у меня есть этот массив:

5, 16, 10, 3, 5, 11

Сумма 10 + 3 + 5 = 18, деленная на размер n (= 6) сбез остатка.

Я не знаю, как это сделать, но я знаю, что необходим массив по модулю.

Есть предложения?

Answer 1

Сохранить массив префиксной суммы по модулю n, давайте назовем этот массив pref_sum []

pref_sum[i] будет содержать сумму A[j] по модулю n, где 0 <= j <= i

Сумма подмассива [i, j] делится на n, если pref_sum[i] - pref_sum[j - 1] modulo n = 0.

Так что для i с pref_sum[i] = x мы должны найти j, где pref_sum[j - 1] = x.

Его можно найти в O (1), если мы сохраним его в хеш-таблице или простом массиве.