Algoritmo ottimale necessario per trovare le coppie divisibili per un dato intero k

Question

Dato n interi e un intero k, indicare quante coppie di questi n interi sono presenti in modo tale che la somma dei due elementi nella coppia sia divisibile per k?

Non conosco i limiti su n e k. Quindi, per semplicità, supponiamo che n e k non siano molto grandi.

Va da sé, dare la soluzione ottimale possibile. (Conosco il metodo ingenuo :-)!)

Answer 1

Se la somma di due numeri è divisibile per k dipende solo dal resto modulo modulo k.

Quindi se k è ragionevolmente piccolo, è sufficiente contare quanti numeri hanno ogni resto possibile e calcolare il numero di coppie da quello. Supponendo k > 0 e tutti i numeri interi non negativi

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; 
} 

fa il lavoro in O(n+k) passi. Se n è piccolo e k molto grande, l'algoritmo ingenuo è migliore.

Answer 2

In aggiunta a ciò che dice Daniel Fischer, se k è molto grande, è possibile ordinare i numeri mod k, e quindi percorrere la lista ordinata da entrambe le estremità (dopo aver affrontato i valori 0 mod k) verso il centro (k/2 mod k). Quello è O (n log n), che è meglio di O (n^2), assumendo che il tuo algoritmo ingenuo sia davvero ingenuo.