algorithm - 与えられた整数 k で割り切れるペアを見つけるために必要な最適アルゴリズム

Question

n 個の整数と整数 k が与えられたとき、ペアの 2 つの要素の合計が k で割り切れるような、与えられた n 個の整数のペアがいくつ存在するか教えてください。

n と k の境界がわかりません。したがって、簡単にするために、n と k はそれほど大きくないと仮定します。

言うまでもなく、可能な限り最適なソリューションを提供します。(単純な方法は知っています :-) ! )

Answer 1

2つの数値の合計が除算可能かどうかは、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、単純なアルゴリズムの方が適しています。

Answer 2

Daniel Fischer の言うことに加えて、k が非常に大きい場合、数値を mod k でソートし、ソートされたリストを両端から (0 mod k 値を処理した後) 中央 (k/2 mod k ）。これは O(n log n) であり、O(n^2) よりも優れています。単純なアルゴリズムが本当に単純であると仮定します。