查找子集是一個數字

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

，你可以有效地組通過存儲包含數字，鍵上模列表的哈希表中的數字。