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?

CodePudding user response：

Some issues:

• There is no reason why base should not be allowed to be 10 or more
• Trying with upperPower 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");

CodePudding user response：

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))