4
\$\begingroup\$

I wrote a function that takes a number and finds the next palindromic number. Time complexity is currently O(n2), which is really bad. How could one make this function more efficient?

function nextPalindrome(n) {
  // first we create a function to check if a single number is a palindrome
  function isPalindrome(num) {
    const forward = num.toString();
    let backward = [];
    for (let i = forward.length - 1; i >= 0; i--) {
      backward.push(forward[i]);
    }
    backward = backward.join('');
    return forward === backward;
  }
  // now let's create a counter variable to increment our number (n)
  // we'll initialize it as n + 1 since we know we're not going to check the first number
  let countUp = n + 1;
  // we also need a nextPalindrome variable
  let nextP;
  // now we need to begin some sort of loop
  // perhaps a while loop will do
  while (true) {
    if (isPalindrome(countUp)) {
      return countUp;
    } else {
      countUp += 1;
    }
  }

}
\$\endgroup\$
  • 2
    \$\begingroup\$ I haven't written the code yet, but here's a hint for you: Try to write a long ordered sequence of palindrome numbers and figure out whether you can solve the problem analytically. \$\endgroup\$ – Igor Soloydenko May 29 '18 at 17:41
  • 1
    \$\begingroup\$ Note: I made a small change to the algorithm after I found a scenario it didn't cover (I changed the loop condition to always iterate over the whole array of digits). \$\endgroup\$ – Máté Safranka May 29 '18 at 22:48
4
\$\begingroup\$

Note: Minor change to the algorithm after I found a scenario it didn't cover

This is more of a mathematical problem than a programming one. After some thinking and experimentation, I've come up with an algorithm that can solve this in O(n), where n is the number of digits in the starting number. The basic principle is that we first break down the number into an array of digits, then start at the two ends and work our way inward to the middle, trying to set each pair of digits to the lower one, or as close to the lower one, in as many places as possible.

When examining a pair of digits, we always override the lower-order digit with the higher-order one. If the lower-order digit is greater than the higher-order one, it means the value of our number has reduced as a result of the override, so we set a carry flag. This carry flag will cause the next digit we measured from the lower end of the number (i.e. the lower-order one if we're less than halfway through the number, and the higher-order one if we're more than halfway through) to increment by one before the override is made. If this incrementation causes the digit to "overflow" into 10, we immediately set the digit to 0, set the carry flag to true, and proceed to the next digit.

function nextPalindrome(n) {
    let digits = [];
    let m = n;
    while (m > 0) {
        digits.unshift(m % 10);
        m = Math.trunc(m / 10);
    }

    let carryFlag = false;
    let midPoint = Math.floor(digits.length / 2);

    for (let i = 0; i < digits.length; i++) {
        let copyFrom = digits[i];
        let copyTo = digits[digits.length - 1 - i] + carryFlag;
        if (copyTo === 10) {
            digits[digits.length - 1 - i] = 0;
            carryFlag = true;
        }
        else {
            let digit = (i < midPoint) ? copyFrom : copyTo;
            carryFlag = copyTo > digit;
            digits[i] = digits[digits.length - 1 - i] = digit;
        }
    }

    return digits.reduce((acc, next) => 10 * acc + next, 0);
}

I don't have a pure mathematical proof detailed, but it seems to work. Please feel free to test it (especially with edge cases) and comment if something's wrong.

\$\endgroup\$
1
\$\begingroup\$

Not sure what you are trying (micro optimization?), but finding the next palidromic number can be simplified as follows. I think it's O(n), but I'm not that versed in Big O.

const isPalindrome = number => {
    // stringify
    // note: no need to split, because a String is indexed
    number += "";
    const len = number.length - 1;
    for (let i = 0; i < len + 1; i += 1) {
      // return false immediately if not equal saves time
      if (number[i] !== number[len-i]) { return false; }
    }
    return true;
};
// use recursion
const nextPalindromeNumber = n => 
  isPalindrome(n) && n || nextPalindromeNumber(n + 1);

// implementation, timed
let range = {start: 10, end: 1000000};
let pNumbers = [];
const start = performance.now();
while (range.start < range.end) {
  range.start = nextPalindromeNumber(range.start);
  pNumbers.push(range.start);
  range.start += 1;
}

// reporting
const done = ((performance.now() - start)/1000).toFixed(3);
document.querySelector("#result").textContent = `
  Palindromic numbers from 10-${range.end.toLocaleString()}: found ${
    pNumbers.length} numbers.
  This took ${done} seconds (${done * 1000}ms).
  The palindromic numbers are\n  ${pNumbers.join("\n  ")}`;
<pre id="result"></pre>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.