Intermedio 0 resueltos 0% de aceptación

Números amigos

Enumera todas las parejas de números amigos en las que ambos números son menores o iguales que un límite.

Lo que aprenderás

  • Construir una tabla con la suma de divisores propios de cada número hasta un límite
  • Comprobar una condición de pareja en ambas direcciones
  • Evitar listar una pareja dos veces o incluir números perfectos

Problema

Ver original (inglés)

Sea s(n) la suma de los divisores propios de n (sus divisores distintos del propio n). Dos números distintos a y b son números amigos cuando s(a) = b y s(b) = a. La pareja más pequeña es 220 y 284: s(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284 y s(284) = 1 + 2 + 4 + 71 + 142 = 220.

Implementa amicable_pair(limit).

Calcular s(n) para cada n hasta limit, uno por uno, es lento. Una criba funciona mejor: para cada d, suma d a cada múltiplo de d mayor que d.

Entrada

limit: el valor máximo que puede tener cualquiera de los dos números de una pareja.

Salida

Devuelve una lista de parejas [a, b] con a < b ≤ limit, ordenadas por a de forma ascendente. Una pareja se incluye solo si ambos números son menores o iguales que limit. Los números perfectos (con s(n) = n) no forman pareja. Si no hay ninguna, devuelve una lista vacía.

Restricciones

1 ≤ limit ≤ 200,000

Ejemplos

Ejemplo 1
Entrada:
limit = 1500

Salida esperada:
expected = [
    [220, 284],
    [1184, 1210]
]
Entrada:
long long limit = 1500;

Salida esperada:
std::vector<std::vector<long long>> expected = {
    {220, 284},
    {1184, 1210}
};
Entrada:
long limit = 1500;

Salida esperada:
long[][] expected = new long[][] {
    new long[] {220, 284},
    new long[] {1184, 1210}
};

Explicación

s(220) = 284 y s(284) = 220, y además s(1184) = 1210 y s(1210) = 1184. Las dos parejas caben por debajo de 1500: [[220, 284], [1184, 1210]].

Ejemplo 2
Entrada:
limit = 250

Salida esperada:
expected = []
Entrada:
long long limit = 250;

Salida esperada:
std::vector<std::vector<long long>> expected = {};
Entrada:
long limit = 250;

Salida esperada:
long[][] expected = new long[][] {};

Explicación

220 no pasa de 250, pero su pareja 284 sí, así que ninguna pareja cabe: [].

Cómo abordarlo

Inténtalo primero por tu cuenta y luego abre las pistas una a una.

Pista 1

Para cada d de 1 a limit / 2, suma d a las sumas de 2d, 3d, 4d, etc.

Pista 2

Para cada a, sea b la suma de sus divisores; comprueba que b esté dentro del rango y que la suma de los divisores de b sea a.

Pista 3

Exigir a < b hace que cada pareja aparezca una sola vez y deja fuera los números perfectos.

Complejidad esperada

tiempo O(limit log limit), espacio extra O(limit)

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.