Вычисление суммы больших мощностей

Question

У меня есть следующая проблема. У меня есть массив, который содержит полномочия -2.

Например, (3,4,5)

мне нужно вычислить сумму этих сил, поэтому ответ: (-2)^3 + (-2)^4 + (-2)^5 = -8 + 16 -32 = -24.

Если абсолютное значение суммы больше 1000000, -1 должно быть возвращено.

Временная сложность алгоритма должна быть O (N * log (N)), а пространственная сложность - O (N).

Уловка состоит в том, что длина массива составляет до 100 000 элементов, и каждый элемент может составлять до 1 000 000 000.

Я не знаю, как это решить. Не могли бы вы посоветовать?

Answer 1

Соберите нечетные степени и четные степени и опишите их как двоичные сегменты (после разделения дубликаты могут быть просто обработаны по принципу 2^n + 2^n = 2^(n + 1)). Концептуально вычесть меньшее число из большего (большее будет иметь самый дальний 1 в не разделяемой позиции). Например,

(-2)^4 => { (0,3) 0; (4,4) 1 } 
(-2)^3 + (-2)^5 => { (0,2) 0; (3,3) 1; (4,4) 0; (5,5) 1 } 

Subtract the first from the second: 
    the segment starting at (4,4) borrows one 1 from the next segment. 

{ (0,2) 0; (3,3) 1; (4,4) 1 } => 11000 

Perform the 1048576 test by checking for any exponents (set 1's) above 19. 

If the number is below 1048576, it can be easily converted from the 
segment list and output if it is lower than 1000001. 

Answer 2

Вы можете просто использовать exponentiation by squaring, чтобы каждый (-2)^N у вас был в O (log n). Таким образом, временная сложность O (n log n). Сложность пространства зависит от длины входной таблицы, так что это O (n).