查找子集是一个数字

Question

问题的倍数：给定的阵列A其表示在一条线上的点，例如[5,-4,1,3,6]，和若干M=3，发现点的内A最大子集，其相互间的距离是M的倍数。

在该示例中，两个可能的子集将是[-4,5]（距离9）和[3,6]（距离3）。

明显的蛮力解决方案是计算O(N^2)时间内每对点之间的距离，然后通过增量构建子集来构建一组候选项。

有没有更有效的解决方案？

Answer 1

遍历所述阵列中的数字和计算每个的模量M和基团通过的结果。最大的组是最大的子集。

例如[5,-4,1,3,6]会给[2,2,1,0,0]

你必须照顾你如何处理负数，为底片模操作定义differently in some languages（如PHP）给他人，但你想MOD（-4，3）以评估2，不是-1。对于底片，你可以计算出它作为（M - （-x MOD M））模m

，你可以有效地组通过存储包含数字，键上模列表的哈希表中的数字。