How to determine a perfect power efficiently?

Challenge: Training on Closest Perfect Power | Codewars

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?

Your solution is not working because it goes into an infinite loop for certain numbers and produces incorrect results for others. Here are two of the test cases:

assert.deepEqual(closestPower(462.5),441);

Your solution is returning 512.

assert.deepEqual(closestPower(2176782359),2176782336);

This causes an infinite loop in the while (!verifyObj.upper || !verifyObj.lower) loop.

I was able to solve this problem with one loop (I used a for loop). You are on the right track with your first while loop, but why did you stop at 10? Certainly bigger numbers are going to have a base bigger than 10 don’t you think? (I’ll give you a hint, the base for the test of 462.5 above is 21.) What do you think is going to be the biggest base you need to check for any given number?

In that loop you are finding the exponent for each base. This seems like a good idea. But then you are only testing if base ** exponent is exactly equal to num. Are you sure you can’t do something with answers that aren’t exactly correct? Remember, it doesn’t have to be a perfect match, we are trying to find the closest perfect power, in other words, the smallest distance between a perfect power and num. Yes, you need to track the correct perfect power value in order to return it, but it’s the distance between that number and num that is the real key to this algorithm.

1 Like