Cuando los números salen a bailar: Divisible Sum Pairs

Hay retos que parecen pedir fuerza bruta, como si fueran una pista de baile sin coreografía. El problema Divisible Sum Pairs de HackerRank es uno de esos: te da un arreglo de números y un divisor k, y te pide contar cuántos pares (i, j) cumplen que i < j y (ar[i] + ar[j]) mod k = 0.

Al principio, mi instinto fue el de todo programador que llega temprano a la fiesta: probar todos los pares posibles. Si dos números suman algo divisible entre k, los contamos. Simple, directo... y terriblemente lento.

La versión "obvia"

Pros:
• Es intuitiva: literalmente pruebas todos los pares.
• Funciona: devuelve el resultado correcto.

Contras:
• Complejidad O(n²): cada número se compara con todos los anteriores.
• Escala mal: si el arreglo crece, el algoritmo se convierte en un baile de tortugas.
• Repite cálculos innecesarios: cada residuo se evalúa una y otra vez.

El análisis con IA

Cuando le mostré esto a Claude, me respondió con una solución que parecía salida de otro planeta. En lugar de comparar todos los pares, me habló de residuos que se complementan.

Su propuesta:

Al principio me pareció extraña. ¿Por qué hablar de residuos si el problema trata de sumas? Pero luego entendí: los residuos son los verdaderos protagonistas del baile.

La fiesta de los residuos

Imagina que los números son invitados en una fiesta temática. Cada uno llega con un número en la frente: su residuo al dividirse entre k.

• Los que traen un 0 bailan entre ellos.
• Los demás buscan pareja: si alguien tiene un 1, necesita encontrar a alguien con un k-1; si alguien tiene un 2, busca un k-2, y así sucesivamente.
• Cuando se encuentran, hacen "match" y se cuentan como un par válido.

Mi primera solución era como revisar manualmente cada pareja en la pista. La optimizada, en cambio, es como tener un registro en la entrada: cada vez que llega un invitado, verificas si su pareja complementaria ya está dentro. Si sí, ¡boom!, se suma al contador.

La teoría detrás del baile

Lo anterior se llama aritmética modular y fue formalizada por Carl Friedrich Gauss en 1801 en su obra Disquisitiones Arithmeticae. Antes de él, Fermat, Euler y Legendre ya habían jugado con propiedades de divisibilidad, pero Gauss fue quien organizó todo en un sistema coherente.

Su notación a ≡ b (mod m) cambió la historia: permitió entender que los residuos no son "sobras", sino identidades equivalentes dentro de un sistema cerrado.

En este problema, la clave está en que dos números a y b cumplen (a + b) % k = 0 si sus residuos se complementan:

• r₁ + r₂ ó
• ambos son 0.

Lo que Gauss descubrió como una estructura matemática hoy se usa en criptografía, relojes, calendarios y, claro, en algoritmos que cuentan parejas sin sudar.

Comparación de estilos

Aspecto	Fuerza bruta	Optimizado
Complejidad	O(n2)	O(n)
Claridad	Intuitiva pero repetitiva	Requiere entender residuos
Escalabilidad	Mala	Excelente
Elegancia	Baja	Alta
Metáfora	Organizador que revisa cada pareja	Registro con lista de complementos

Conclusión

La fuerza bruta funciona, pero no baila bien. La versión optimizada usa la aritmética modular para convertir el caos en ritmo. Es el tipo de solución que te hace sentir que los números no solo obedecen reglas: también tienen estilo.

Epílogo: Gauss, el DJ de la fiesta

La música baja, las luces giran, y en la cabina aparece Carl Friedrich Gauss, el matemático que en 1801 decidió que los números también merecían una pista de baile. Con su obra Disquisitiones Arithmeticae, Gauss inventó la regla que todos seguimos en esta fiesta: los residuos no son sobras, son identidades.

Fermat y Euler habían dejado los instrumentos tirados por ahí, pero Gauss los afinó y puso orden. Desde entonces, cada número sabe con quién bailar: los ceros entre ellos, los unos con los doses, y así hasta completar el ritmo de k.

Hoy, cada vez que un algoritmo usa aritmética modular —ya sea para cifrar mensajes, calcular horarios o resolver retos de HackerRank—, Gauss sigue en la cabina, mezclando congruencias y divisibilidad como si fueran beats.