从给定的 N 个整数中找出有多少个不同的三元组数字的总和可被整数 M 整除

Question

给定 N 个整数。三元组数字是一组三个数字，其总和可以被常数 M 整除。从给定的 N 个整数中找出有多少不同的数字三元组的总和可以被 M 整除。找到此问题答案的最佳算法是什么？

请注意：每个元素都被视为不同的，无论它们的实际值如何。

This is the link to the actual problem

Answer 1

我会首先计算每个数字除以 M 后的 remainder。然后我会根据它们的余数对所有 N 个数字进行排序。

这是 N*log(N) 的成本。

然后对于每对数字，我将搜索所有数字中是否存在匹配的余数，这将使我的和能被 M 整除。

有 N^2 对，每次查找都是二分查找 - log(N)。

所以我看到解决方案的成本为 N^2*log(N)，但也许有更复杂、更便宜的解决方案。

Answer 2

有一个 O(N + M^2) 的解决方案。

首先创建一个数组 C[M]，其中 C[i] 包含第 i mod M 个输入数字。这需要 O(N) 时间。

然后对于每个 i <= j <= k 且 i+j+k=0 mod M，计算三元组 (a, b, c) 且 a=i (mod M ), b=j (mod M), c=k(mod M).

我们可以通过遍历 i 和 j 并找到导致总和为 0 (mod M) 的唯一 k 来高效地完成此操作，如果 k

这是完整的代码，它为给定的测试用例生成正确答案 26：

def choose2(n):
    return n * (n-1) // 2

def choose3(n):
    return n * (n-1) * (n-2) // 6

def triples(A, M):
    C = [0] * M
    for a in A:
        C[a % M] += 1
    T = 0
    for i in range(M):
        for j in range(i, M):
            k = (-i - j) % M
            if k < j:
                continue
            if i == j == k:
                T += choose3(C[i])
            elif i == j:
                T += choose2(C[i]) * C[k]
            elif j == k:
                T += C[i] * choose2(C[j])
            else:
                T += C[i] * C[j] * C[k]
    return T

print(triples([1, 10, 4, 3, 2, 5, 0, 1, 9, 5], 5))

从给定的 N 个整数中找出有多少个不同的三元组数字的总和可被整数 M 整除

Find out how many distinct triplets of numbers, from give N integers , have their sum divisible by integer M

algorithm

hashtable