es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Codewars RuntimeError Error en tiempo de ejecución de Codewars

Actualmente estoy tratando de resolver el problema “¿Está mi amigo engañando?” en Codewars.
El texto son los detalles del problema:

Un amigo mío toma la secuencia de todos los números del 1 al n (donde n>0).

Dentro de esa secuencia, elige dos números, a y b.

Él dice que el producto de a y b debe ser igual a la suma de todos los números en la secuencia, excluyendo a y b.

Dado un número n, ¿podrías decirme los números que excluyó de la secuencia?
La función toma el parámetro: n (n siempre es estrictamente mayor que 0) y devuelve una matriz o una cadena (dependiendo del lenguaje) de la forma:

[(a, b), …] or [[a, b], …] or {{a, b}, …} or or [{a, b}, …]

con todos los (a, b) que son los posibles números eliminados en la secuencia del 1 al n.

[(a, b), …] or [[a, b], …] or {{a, b}, …} or … se ordenará en orden creciente del “a”.

Sucede que hay varios posibles (a, b). La función devuelve una matriz vacía (o una cadena vacía) si no se encuentran números posibles, lo que demostrará que mi amigo no ha dicho la verdad! (Go: en este caso, devolver nil).

Ejemplos:

removNb(26) debería devolver [(15, 21), (21, 15)]
o
removNb(26) debería devolver { {15, 21}, {21, 15} }
o
removeNb(26) debería devolver [[15, 21], [21, 15]]
o
removNb(26) debería devolver [ {15, 21}, {21, 15} ]
o
removNb(26) debería devolver “15 21, 21 15”

o

en C:
removNb(26) debería devolver {{15, 21}{21, 15}} probado mediante cadenas.
La función removNb debe devolver un puntero a un array de punteros de tipo Pair, cada uno también asignado.

Mi código que intenté resolver el problema:

def removNb(n):
lista = [i+1 for i in range(n)]
resultado = []
for k in range(n):
for t in range(k,n):
m,n = lista[k], lista[t]
if m * n == sum(lista)-(m+n):
resultado.append((m, n))
resultado.append((n, m))
return resultado

Esta solución funciona, pero aparentemente no está optimizada lo suficiente.

¿Alguien tiene alguna idea de cómo optimizar aún más el código?

Tags:  , ,

Answer

  1. Avatar for davy.ai

    Una posible estrategia de optimización podría ser reducir el espacio de búsqueda utilizando conocimientos matemáticos. Por ejemplo, sabemos que la suma de todos los números del 1 al n es igual a (n * (n+1)) / 2. Por lo tanto, podemos calcular la suma objetivo que el producto de a y b debe ser igual, y enfocar nuestra búsqueda en pares de números que suman esta suma objetivo. Esto reduciría significativamente la cantidad de pares que deben ser verificados y mejorar el tiempo de ejecución de la función.

    Otra estrategia de optimización podría ser utilizar un enfoque de dos punteros para iterar a través de la lista de números desde ambos extremos, convergiendo gradualmente hacia el centro. Esto nos permitiría salir temprano si ya hemos encontrado todos los pares válidos y también evitar cálculos innecesarios al ignorar pares que claramente son demasiado pequeños o demasiado grandes.

    Implementar ambas estrategias probablemente resultaría en una solución mucho más rápida.

Comments are closed.