Dados n enteros y un número entero k, indique cuántos pares de los n enteros dados existen, de modo que la suma de los dos elementos en el par es divisible por k?Algoritmo óptimo necesario para encontrar pares divisibles por un número entero dado k
No conozco los límites en ny k. Por lo tanto, en aras de la simplicidad, supongamos que n y k no son muy grandes.
No hace falta decir, brinde la mejor solución posible. (Sé el método ingenuo :-)!)
Si la suma de dos números es divisible por k solo depende de sus residuos módulo k.
Así que si k es razonablemente pequeño, puede contar cuántos números tienen cada resto posible y calcular el número de pares a partir de eso. Suponiendo k > 0 y todos los enteros no negativos
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;
}
hace el trabajo en O(n+k) pasos. Si n es pequeño y k muy grande, el algoritmo ingenuo es mejor.
Además de lo que dice Daniel Fischer, si k es muy grande, puede ordenar los números mod k, y luego recorrer la lista ordenada desde ambos extremos (después de tratar con los valores de 0 mod k) hacia el centro (k/2 mod k). Eso es O (n log n), que es mejor que O (n^2), suponiendo que su ingenuo algoritmo es realmente ingenuo.
Mi Naive involucró la Búsqueda Binaria ... Así que también sería O (n log n) pero sí, su versión es una mejora ... ya que solo involucra O (n log n) para la clasificación ... y lo hace en lineal O (n) tiempo en lugar de O (n log n) utilizando la búsqueda binaria. Gracias ! +1 :) – user1599964
Puede usar una tabla hash en lugar de ordenar/búsqueda binaria para obtener O (n). –
@KeithRandall, sí, podrías intentarlo. Esperaría que mi solución fuera generalmente más rápida, porque su ciclo interno es muy rápido, pero podría estar equivocado. Si quieres probarlo, te sugiero que un buen hash para un entero k mod sea el entero mod k mod p donde p es un primo cercano a n. Eso mantiene el almacenamiento en O (n), que es competitivo con búsqueda y escaneo. (Usar el entero mod k en sí mismo, por supuesto, no garantizaría ninguna colisión, pero luego redujo el problema a Daniel Binsort, y lo descartamos en este caso porque los contenedores ocupan demasiada memoria). – rici
Me ganaste :) Sin embargo, quieres usar los conteos [], no arr [] donde estás peinando, y debes considerar los recuentos [0] – rici
¡Genial! Tiempo lineal ... eso es lo que estaba buscando ... ¡Gracias! – user1599964
@rici Gracias por el aviso. 'counts [0]' se usa en la inicialización de 'peines', no lo olvide (pero tuve otro error tipográfico,' k-1' en lugar de 'k-i'). –