7
\$\begingroup\$

I recently did a programming challenge: given a positive number find the next palindromic number. In PHP, I decided to do something like this:

<?php

function palindromic($input) {
  while (1) {
    $number = (string) ++$input;

    if ($number == strrev($number)) {
      return $number;
    }
  }
}

I was then asked to provide test inputs for the function and to explain why, so I had (where x is a random number)

  • x < 10: test single digits
  • 10 < x < 100: tests numbers with even length
  • 100 < x < 1000: tests numbers with odd lengths
  • 1,000,000 < x: tests a largish number

Note: we can always assume a positive number, so checking for non-positive numbers or inputs that are a different type, or asserting exceptions thrown back, etc aren't relevant to the challenge.

Apparently there were some other important numbers to test, can anyone explain what I've missed here?

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

I don't code in java or python so I don't fully follow the methods provided in the commented link under the question.

I've decided to write a method that avoids the incremental checking for palindromic integers. Instead, it uses arithmetic based on a few preliminary string function results to discover the closest greater palindromic integer. Note, there are limitations to my method because the input and output are integers rather than strings. I can conclude after testing that my method will stay true into the 10's of trillions.

Code: (Demo)

function nextPalindromicInteger($integer) {
    if ($integer < 9) {
        $next = $integer + 1;
        return "$integer => $next (+1) " . ($next != strrev($next) ? "FAIL" : "PASS") . "\n";
    }
    $size = strlen($integer);
    $psize = ceil($size / 2);  // find length of rhs & lhs including pivot when length is odd
    $npsize = $size - $psize;  // find length of rhs & lhs excluding pivot when length is odd
    $rnplhs = (int)strrev(substr($integer, 0, $npsize));  // reverse nplhs
    $nprhs = (int)substr($integer, -$npsize);  // store right hand side integer excluding pivot  //KEEP
    $trimmed=strlen(rtrim(substr($integer, 0, $psize), '9')); // store length of rtrim'd plhs
    if ($rnplhs > $nprhs) {
        $bump = 0;
    } elseif (!strlen(trim($integer, '9'))) {
        $bump = 2;
        $nprhs = 0;
        $rnplhs = 0;
    } else {
        if ($psize != $npsize) {  // odd integer length
            if ($trimmed == 1) {
                $exponent = 1;  // dictates $bump=11
            } else {
                $exponent = $npsize;
            }
        } else {  // even integer length
            $exponent = $trimmed;
        }
        $bump = pow(10, $exponent);
        if ($psize == $npsize || $trimmed < $psize) {
            $bump += pow(10, $exponent - 1);
        }
    }
    $next = $integer + $rnplhs - $nprhs + $bump;
    return "$integer => $next (+" . ($next - $integer) . ") " . ($next != strrev($next) ? "FAIL" : "PASS") . "\n";
}
for ($x = 0; $x < 14; ++$x) {
    $integer = rand(pow(10, $x), pow(10, $x + 1) - 1);
    echo nextPalindromicInteger($integer);   
}

If I spent some more time refining, I could probably write my function more eloquently, but for the purposes of this question it is sufficient to reveal (to me at least) some of the fringe cases.

I found in my development and testing that it was important to test against:

  • a range of integers, some with even length and some with odd length.
  • integers with a pivot (shared middle digit) of nine.
  • integers with an odd length and a non-9 pivot.
  • integers consisting entirely of 9's.
  • integers where the reversed left-hand-side component minus the right-hand-side component is: >0, =0, and <0

Once I isolated the patterns that exist with certain sequences, I could declare the correct "bump" or adjustment. Some bumps are static, others depend on the length or value of the left-hand-side component.

As for your relevant numbers to check using your method, I can't think of any that would cause trouble because you are looping and checking each iteration. Perhaps the challenge was assuming that you would try to write a method without loops as I did or run "inside out" string comparison checks on each side's digits.

As for checking "large-ish" numbers, I found that once I had perfected the bumps from 1 to 9999, all integers above that were accounted for.

Possible Output:

9 => 11 (+2) PASS
75 => 77 (+2) PASS
776 => 777 (+1) PASS
4891 => 4994 (+103) PASS
92764 => 92829 (+65) PASS
999539 => 999999 (+460) PASS
7059657 => 7060607 (+950) PASS
48756572 => 48766784 (+10212) PASS
633149324 => 633151336 (+2012) PASS
2096785014 => 2096886902 (+101888) PASS
80448359477 => 80448384408 (+24931) PASS
237762850363 => 237763367732 (+517369) PASS
7730351516591 => 7730351530377 (+13786) PASS
79541453924626 => 79541455414597 (+1489971) PASS
\$\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.