Closest Palindrome Number

Question

I came across one of the common interview question which was to find the closest palindrome number. Say if the input is 127 then output will be 131 and if it is 125 then it should give 121 as output.

I can come up with the logic but my logic fails on certain cases like 91, 911. In these inputs it give 99 , 919 but the correct output is 88 and 909.

Algorithm steps are:

• Convert the number into string.
• copy first half to second half in reverse order
• convert to number and measure the abs. difference with original number diff1
• add 1 to half string and now copy first half to second half in reverse order
• convert to number and measure the abs. difference with original number diff2
• if diff1 is less than diff2 return first number else return second number

Answer 1

This is actually an interesting problem. Obviously what you want to do to make this more than just a brute force is to use the most significant digits and put them in the least significant digit locations to form a palindrome. (I'm going to refer to the difference between the palindrome and the original as the "distance")

From that I'm going to say that we can ignore the least significant half of the numbers because it really doesn't matter (it matters when determining the distance, but that's all).

I'm going to take an abstract number: ABCDEF. Where A,B,C,D,E,F are all random digits. Again as I said D,E,F are not needed for determining the palindrome as what we want is to mirror the first half of the digits onto the second half. Obviously we don't want to do it the other way around or we'd be modifying more significant digits resulting in a greater distance from the original.

So a palindrome would be ABCCBA, however as you've already stated this doesn't always you the shortest distance. However the "solution" is still of the form XYZZYX so if we think about minimizing the "significance" of the digits we're modifying that would mean we'd want to modify C (or the middle most digit).

Lets take a step back and look at why: ABCCBA

• At first it might be tempting to modify A because it's in the least significant position: the far right. However in order to modify the least significant we need to modify the most significant. So A is out.
• The same can be said for B, so C ends up being our digit of choice.

Okay so now that we've worked out that we want to modify C to get our potentially closer number we need to think about bounds. ABCDEF is our original number, and if ABCCBA isn't the closest palindrome, then what could be? Based on our little detour above we can find it by modifying C. So there are two cases, ABCDEF is greater than ABCCBA or that is less than ABCCBA.

If ABCDEF is greater than ABCCBA then lets add 1 to C. We'll say T = C+1 so now we have a number ABTTBA. So we'll test to make sure that ABCDEF - ABCCBA > ABCDEF - ABTTBA and if so we know that ABTTBA is the nearest palindrome. As any more modifications to C would just take us more and more distant.

Alternately if ABCDEF is less than ABCCBA then we'll subtract 1 from C. Let's say V = C-1. So we have ABVVBA, which just like above we'll test: ABCDEF - ABCCBA > ABCDEF - ABVVBA and you'll have the same solution.

The trick is that ABCDEF is always between ABTTBA and ABVVBA and the only other palindrome between those numbers is ABCCBA. So you only have 3 options for a solution. and if you compare ABCDEF to ABCCBA you only need to check 2.

I don't think it will be hard for you to adapt this to numbers of any size. and in the case of an odd number of digits you'd simply have ABCBA, ABVBA and ABTBA and so on...

So just like your examples: lets take 911.

1. Ignore the last 1 we only take the first half (round up). so 91X.
2. Replace X with 9. we have 919. this is out mid point.
3. We know our original 911 is less than 919 so subtract 1 from our middle number so we get our second (lower bound) 909.
4. Compare 911 - 919 and 911 - 909
5. return the one with the smallest difference.

So this gives us a constant time algorithm :) As pointed out in the comments this is not constant time in the worst case (oops), but is certainly better than a brute force approach.

This appears to be what you have, but I thought I'd elaborate to hopefully shed light on the issue as it seems to be a small programming error on your part otherwise.

Answer 2

This is an implementation of Naveen's and Don's algorithm. It uses Happy Yellow Face's algorithm as a test oracle.

I would be happy to see people tweak it to remove redundant steps or special cases.

gcc 4.7.3: g++ -Wall -Wextra -std=c++0x nearest-palindrome.cpp

#include <algorithm>
#include <cassert>
#include <iostream>
#include <iterator>
#include <sstream>
#include <string>
#include <vector>

// I do not have std::to_string.
template <class T>
std::string to_string(const T& v) {
  std::stringstream ss;
  ss << v;
  return ss.str(); }

// Nor do I have std::stoi. :(
int stoi(const std::string& s) {
  std::stringstream ss(s);
  int v;
  ss >> v;
  return v; }

bool isPalindrome(int n) {
  const auto s = to_string(n);
  return s == std::string(s.rbegin(), s.rend()); }

int specNearestPalindrome(int n) {
  assert(0 <= n);

  int less = n, more = n;
  while (true) {
    if (isPalindrome(less)) { return less; }
    if (isPalindrome(more)) { return more; }
    --less; ++more; } }

std::string reflect(std::string& str, int n) {
  std::string s(str);
  s.resize(s.size() + n);
  std::reverse_copy(std::begin(str),
      std::next(std::begin(str), n),
      std::next(std::begin(s), str.size()));
  return s; }

bool isPow10(int n) {
  return n < 10 ? n == 1 : (n % 10 == 0) && isPow10(n / 10); }

int nearestPalindrome(int n) {
  assert(0 <= n);
  if (n != 1 && isPow10(n)) { return n - 1; }  // special case

  auto nstr = to_string(n);
  // first half, rounding up
  auto f1 = nstr.substr(0, (nstr.size() + 1) / 2);
  auto p1 = stoi(reflect(f1, nstr.size() / 2));

  const auto twiddle = p1 <= n ? 1 : -1;
  auto f2 = to_string((stoi(f1) + twiddle));
  auto p2 = stoi(reflect(f2, nstr.size() / 2));

  if (p2 < p1) { std::swap(p1, p2); }
  return n - p1 <= p2 - n ? p1 : p2; }

int main() {
  std::vector<int> tests = { 0, 1, 6, 9, 10, 11, 12, 71, 74, 79, 99, 100, 999, 1000, 9900, 9999, 999000 };

  for (const auto& t : tests) {
    std::cout <<
      (nearestPalindrome(t) == specNearestPalindrome(t) ? "." : "X");
  }
  std::cout << std::endl;

  return 0; }

Answer 3

Here is a generic algorithm that would work¹, although using brute-force:

int findNearestPalindrome(int n) {
    int less = n;
    int more = n;
    while(true) {
        if (isPalindrome(less)) return less;
        if (isPalindrome(more)) return more;
        --less;
        ++more;
   }
}

WithinisPalindrome() function, all you need to do is convert the number to a string, and then compare the string with itself reversed.

¹_{However, this wouldn't check for tie cases, like Ted Hopp commented. You'd have to make a few changes to make it tie-recognizable.}