如何检查存储在其中的无限制自然数的和8文件是否可除以8？

Question

我在一次面试中回答了这个问题，正如我所预料的那样，我无法回答。我对面试官采取了一种粗暴的态度，那就是：

1. 在每个文件中添加数字。
2. 每个文件中的数字之和，最后检查它是否可以被8整除。

同时，我告诉他这种方法的缺点，比如Integer溢出和内存问题。

无论如何，我努力思考，但没有成功，因为我没有遇到这类问题，直到现在。

我如何解决上述问题，以及如何发展我的思维过程来解决这些问题？有什么我可以利用的资源吗？

Answer 1

由于这个问题的性质，您需要检查文件中的每个数字。这意味着蛮力基本上是唯一的方法。但是，有一些方法可以提高内存的效率，减少内存泄漏的可能性。下面是一个降低伪码空间复杂度的简单算法的分解：

Read n integers into array
buffer[ len(array) ] = int array
total = 0

for integer i in array:
    if total % 8 == 0:
        total = 0
        remove all elements in buffer from array
    else
        buffer.append(i)
        total += i
    fi
end for

使用此算法，您可以对数字进行求和，直到将它们除以8为止，这时您可以从缓冲区中删除所有这些数字，并读取更多内容。对于像8这样的小数字来说，这是非常好的，特别是对于非常小或非常大的数据文件。不过，我想指出的是，确实存在一组数字，其中没有连续的子数组可以被8整除，换句话说，最坏的情况是空间复杂度仍然是O(n)。不过，这绝对不是一般的情况。

如果您想要更好的空间复杂性，您需要牺牲一点时间，并在代码中添加一些更复杂的内容。我不会对此进行任何伪编码，但实际上您需要将数字(或一组数字)与相应的模数值相匹配。例如，两个整数n和m的和可除以8当且仅当(n%8) + (m%8) == 0,8。例如:5和3，17和15，12和12。

没有什么可以比O(n)更好地获得时间复杂度，但是如果这是一个选项，您可以使用多个线程或进程来分割工作。

Answer 2

这是我第一次读到你的问题，我想到的是最长的非连续子序列可以被k除，但是它不能解决这个大数据。

在我看来，你可以通过计算余数的频率来解决这个问题，而不是所有输入数字的总和。您只需要一个8元素数组(对应于0到7)来存储这些频率，并检查和(i * arrayi，i从0到7)是否可被8整除。

然而，也许数量太大了。你可以注意到，每个数字乘8肯定可以被8整除。所以当计数频率时，如果频率数组中的任何元素达到8，你可以将它重置为0。另外，您可以忘记数组的第0个元素，因为它已经可以被8整除。最后，取(i * arrayi，i从1到7)之和，然后检查它是否可被8整除。

Init array[8] by all 0.

while (there is number remain) 
    read a number tmp
    array[tmp % 8]++;
    if (array[tmp%8] == 8)
        array[tmp%8] = 0
sum = 0
for (i from 1 to 7)
    sum += array[i] * i
if sum % 8 == 0
    output yes
else
    output no

Answer 3

如果您想通过不存储所有数字的和来节省内存，您只需将每个数字的%为8，并将每个余数之和。最后，检查最后的余数之和是否可以除以8。

如果可能的话，您还可以应用8条规则的可分性，即：

如果最后3位数字可被8整除，则数字可被8整除。

所以你也许可以在某种程度上考虑到这一点。请参阅下面@灰胡子的评论。