Estoy tratando de programar una función que toma un entero no negativo y devuelve una lista de pares de enteros no negativos cuyos valores, cuando se elevan al cuadrado, suman el entero dado.
ejemplos:
5 --> [ [1, 2] ] 25 --> [ [0, 5], [3, 4] ] 325 --> [ [1, 18], [6, 17], [10, 15] ]Mi solución funciona en un IDE, pero cuando la envío a Codewars, recibo el error de código de salida 139: ERROR FATAL: error en la asignación de tamaño de tabla no válido: memoria de JavaScript sin memoria. La documentación de codewars indica que esto se debe a un algoritmo ineficiente.
Inicialmente, mi solución contenía un bucle anidado que causaba un tiempo de ejecución prolongado, pero desde entonces he refactorizado mi código para eliminarlo. A pesar de esta complejidad reducida, sigo teniendo el mismo error.
¿Alguna sugerencia de cómo puedo disminuir aún más la complejidad?
const allSquaredPairs = (n) => { //get array of all numbers between 0 and sqrt of n let possibleNums = Array(n) .fill() .map((_, i) => { if ((i + 1) ** 2 <= n) return i + 1; //only numbers lesser than sqrt of n }) .filter(n => n!=undefined) possibleNums = [0, ...possibleNums]; const matchingPairs = []; while (possibleNums.length){ const num1 = possibleNums[0]; const num2 = possibleNums[possibleNums.length-1]; const sum = num1 ** 2 + num2 ** 2 if (sum === n) matchingPairs.push([num1, num2]); if (sum > n ) possibleNums.pop() else possibleNums.shift() } return matchingPairs; }; console.log(allSquaredPairs(25));Su solución asigna una matriz de longitud n y luego itera sobre ella. Eso significa que el requisito de memoria para su solución aumenta linealmente a medida que aumenta n.
Podría implementar esto sin asignar esa matriz para que el requisito de memoria sea constante sin importar cuán grande sea el valor de n.
const examples = [ { input: 5, output: [ [1, 2] ] }, { input: 25, output: [ [0, 5], [3, 4] ] }, { input: 325, output: [ [1, 18], [6, 17], [10, 15] ] }, { input: Number.MAX_SAFE_INTEGER, output: [] } ]; function allSquaredPairs(n) { const matchingPairs = []; const smallestIntegerLargerThanSquareRootOfN = Math.ceil(Math.sqrt(n)); let lowerBound = 0; let upperBound = smallestIntegerLargerThanSquareRootOfN; while (lowerBound < upperBound) { const sum = lowerBound ** 2 + upperBound ** 2; if (sum === n) { matchingPairs.push([lowerBound, upperBound]); lowerBound += 1; } else if (sum < n) lowerBound += 1; else if (sum > n) upperBound -= 1; else console.log("ERROR!") } return matchingPairs; } examples.forEach(({ input, output}) => console.log({ n: input, expected: JSON.stringify(output), " actual": JSON.stringify(allSquaredPairs(input)) })); Como punto de interés, probé esto con let whatever = new Array(n) al comienzo de la función, y para el caso de prueba de entero seguro máximo arrojó RangeError: invalid array length . Ese es un error diferente al que estaba viendo, pero ilustra cómo la asignación de una matriz de longitud n puede complicar las cosas.