Challenge: https://www.codewars.com/kata/57c7930dfa9fc5f0e30009eb/train/javascript
Hi I have been trying this problem for many hours but unfortunately my code is taking too long to pass:
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);
}
I realized that my code is redundant as all i need to know if a “base” and “exponent” are more than 1 to determine a perfect power. Any formulas or ideas?
Some issues:
base should not be allowed to be 10 or moreupperPower at each increment is taking too many iterations. The distance to the next power might be rather big.I would suggest the following algorithm:
Let the exponent to try with start at 2, and then increment by 1. Calculate which could be the corresponding base. The real base can be found by raising n to the inverse exponent (i.e. 1/exp). Then there are only 2 interesting integer bases to consider: by rounding downwards and upwards.
Here is an implementation:
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");Here's my algorithm first i will get the exponent from base that less than of the n then I added the current base of the loop with the n then get the base log.
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))