Desafío: https://www.codewars.com/kata/57c7930dfa9fc5f0e30009eb/train/javascript
Hola, he estado tratando este problema durante muchas horas, pero desafortunadamente mi código está tardando demasiado en pasar:
function closestPower(num) { num = Math.floor(num); if (num < 4) return 4; // check if input is perfect power let base = 2; while (base < 10) { let exponent = Math.trunc(getBaseLog(base , num)); if ( Math.pow(base, exponent) === num ) { return num; } base++; } // check for upper and lower base = 2; const verifyObj = {upper:null, lower:null}; // verify let upperPower = num + 1; let lowerPower = num - 1; while (!verifyObj.upper || !verifyObj.lower) { // no perfect power if (lowerPower <= 2 ) verifyObj.lower = "Not found"; if (upperPower === Infinity ) verifyObj.upper = "Not found"; // up til base 9 if (base === 10) { if (!verifyObj.upper) upperPower++; if (!verifyObj.lower) lowerPower--; base = 2; } // upper if (!verifyObj.upper) { let exponent = Math.trunc(getBaseLog(base , upperPower)); if ( Math.pow(base, exponent) === upperPower ) { verifyObj.upper = upperPower; } } // lower if (!verifyObj.lower) { let exponent = Math.trunc(getBaseLog(base , lowerPower)); if ( Math.pow(base, exponent) === lowerPower ) { verifyObj.lower = lowerPower; } } base++; } console.log(verifyObj) // {upper:64, lower: 49} // nearest power if ((upperPower - num) < (num - lowerPower)) { return upperPower; } else return lowerPower; } closestPower(56.5); // 49 function getBaseLog(x, y) { return Math.log(y) / Math.log(x); }Me di cuenta de que mi código es redundante ya que todo lo que necesito saber es si una "base" y un "exponente" son más de 1 para determinar una potencia perfecta. ¿Alguna fórmula o idea?
Algunos asuntos:
base sea 10 o másupperPower en cada incremento está tomando demasiadas iteraciones. La distancia a la siguiente potencia puede ser bastante grande.Yo sugeriría el siguiente algoritmo:
Deje que el exponente para probar comience en 2 y luego incremente en 1. Calcule cuál podría ser la base correspondiente. La base real se puede encontrar elevando n al exponente inverso (es decir 1/exp ). Entonces solo hay 2 bases enteras interesantes para considerar: redondeando hacia abajo y hacia arriba.
Aquí hay una implementación:
function closestPower(n) { if (n <= 6) return 4; let result = -1; let closest = n; for (let factor, exp = 2; (factor = n ** (1 / exp)) > 1.9; ++exp) { let above = Math.ceil(factor); for (let intfactor = Math.floor(factor); intfactor <= above; intfactor++) { let power = intfactor ** exp; let diff = Math.abs(power - n); if (diff == 0) return n; if (diff < closest || diff == closest && power < n) { closest = diff; result = power; } } } return result; } // Some tests: const tests = [ [0, 4], [9, 9], [30, 32], [34, 32], [56.5, 49], [123321456654, 123321773584] ]; for (let [n, expected] of tests) { let result = closestPower(n); if (result === expected) continue; console.log(`closestPower(${n}) returned ${result}, but expected ${expected}`); } console.log("all tests done");Aquí está mi algoritmo primero, obtendré el exponente de la base que es menor que la n, luego agregué la base actual del bucle con la n y luego obtuve el registro base.
function closestPower(n) { if(n < 4) return 4 let closest = [] let base = 2 while(base < n) { const exponent = Math.floor(Math.log(n + base) / Math.log(base)) const power = Math.pow(base,exponent) if(exponent === 1) break if(power === n) return n closest.push(power) base++ } return closest.reduce((prev, curr) => (Math.abs(curr - n) < Math.abs(prev - n) ? curr : prev)) } console.log(closestPower(0)) console.log(closestPower(9)) console.log(closestPower(30)) console.log(closestPower(34)) console.log(closestPower(56.5)) console.log(closestPower(123321456654))