计算大幂次和

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。

我不知道该如何解决这个问题。你能提供建议吗？

- dedushka

---

这个问题应该发在http://math.stackexchange.com/上。 - H. Pauwelyn

每个指数可以高达10亿，还是每个“2^x”的结果可以高达10亿？ - Juan Lopes

数组是否已排序？它是否可能包含重复项？ - rici

Juan Lopes，每个指数可以高达10亿。rici，数组未排序且可能包含重复项。 - dedushka

你应该给出一个数组元素不连续的例子，因为这会极大地简化问题。或者这些数字总是连续的吗？ - Teepeemm

Answer 1

你可以简单地使用平方求幂算法，这样你就可以在O(log n)的时间内得到每个(-2)^N。因此，时间复杂度为O(n log n)。空间复杂度取决于输入表的长度，因此是O(n)。

- jan_kowalski_314

---

这并不是那么简单。2^n 有 O(n) 位数字，只有在乘法以 O(1) 进行时才为 O(log n)。如果 OP 所说的“每个元素最多可达 10 亿”意味着每个指数最多可达 10 亿，则无法进行 O(1) 乘法。 - Juan Lopes

Answer 2

收集奇数次幂和偶数次幂，并将它们描述为二进制段（一旦分离，重复的可以根据原则简单处理，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.

- גלעד ברקן