查找可被给定整数k整除的对所需的最佳算法

  • Z时代
  • 2024-01-10
  • 分类：问答

给定n个整数和一个整数k，请告诉我们存在多少对给定的n个整数，以便该对中两个元素的总和可被k整除？

我不知道n和k的界限。因此，为简单起见，假设n和k不是很大。

不用说，给出尽可能最佳的解决方案。（我知道天真的方法：-）！）

回答：

两个数的和是否可被除以k仅取决于它们的余数取模k。

因此，如果k相当小，则可以只计算每个可能余数的数量，然后从中计算出对的数量。假定k > 0所有整数均为非负数

unsigned long long combinations(unsigned k, unsigned long long *arr, unsigned n) {
    unsigned long long counts[k] = {0};
    unsigned i;
    for(i = 0; i < n; ++i) {
        ++counts[arr[i]%k];
    }
    // number of pairs where both are divisible by k
    unsigned long long combs = counts[0]*(counts[0]-1)/2;
    for(i = 1; i < (k+1)/2; ++i) {
        combs += counts[i]*counts[k-i];
    }
    if (k == 2*i) {
        combs += counts[i]*(counts[i] - 1)/2;
    }
    return combs;
}

分O(n+k)步完成工作。如果n很小而k很大，那么朴素的算法会更好。

以上是 查找可被给定整数k整除的对所需的最佳算法 的全部内容， 来源链接： utcz.com/qa/405096.html

回到顶部