Closest Palindrome Number

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:

5 Answers
5

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.

ABCDEF

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

ABCCBA

XYZZYX

Lets take a step back and look at why: ABCCBA

ABCCBA

A

A

B

C

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.

C

ABCDEF

ABCCBA

C

ABCDEF

ABCCBA

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.

ABCDEF

ABCCBA

C

T = C+1

ABTTBA

ABCDEF - ABCCBA > ABCDEF - ABTTBA

ABTTBA

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.

ABCDEF

ABCCBA

C

V = C-1

ABVVBA

ABCDEF - ABCCBA > ABCDEF - ABVVBA

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.

ABCDEF

ABTTBA

ABVVBA

ABCCBA

ABCDEF

ABCCBA

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

ABCBA

ABVBA

ABTBA

So just like your examples: lets take 911.

911 - 919

911 - 909

So this gives us a constant time algorithm :)

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.

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; }


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.

isPalindrome()

¹_{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.}

#include <iostream>
#include <cmath>
#include <functional>
#include <limits>
#include <sstream>

// for convience
using namespace std;
using ULL = unsigned long long int;

// calculate the number of digits
auto Len = (auto num) -> ULL {
return floor(log10(num)) + 1; };

// extract left half of number
auto Halfn = (auto num, auto olen) {
for (unsigned i = 0; i < olen / 2; num /= 10, ++i);
return num;
};

int main() {
ULL num; cin >> num;
// some basic checking
if (num < 10) {
cerr << "Error, enter a number >= 10";
return 0;
}

if (numeric_limits<ULL>::max() < num) {
cerr << "Error, number too largen";
return 0;
}
cout << ((auto num) {
auto olen = Len(num);
auto lhalf = Halfn(num, olen);

function<ULL(ULL)> palin = [olen] (auto lhalf) {
auto half = to_string(lhalf);
// this is the mirror string that needs to be
// appended to left half to form the final
// palindrome
auto tmp = half.substr(0, olen / 2);

// take care of a corner case which
// happens when the number of digits in
// the left half of number decrease, while
// trying to find a lower palindrome
// e.g. num = 100000
// left half = 100 , the value passed to the
// function palin, is 99. if all digits are 9
// then we need to adjust the count of 9,
// otherwise if i simply replicate it, i'll get
// 9999 but one more 9 is required for the
// correct output.

if (olen / 2 > tmp.size() &&
all_of(tmp.begin(), tmp.end(),
(auto c) { return '9' == c; })) {
tmp += '9';
}

// append, convert and return
half = half + string(tmp.crbegin(),
tmp.crend());
return stoull(half);
};

auto bpalin = palin(lhalf);
auto hpalin = palin(lhalf + 1);
auto lpalin = palin(lhalf - 1);

stringstream ss;
ss << "base palindrome = " << bpalin <<'n';
ss << "higher palindrome = "<<hpalin <<'n';
ss << "lower palindrome = " << lpalin <<'n';

// calculating absolute difference for
// finding the nearest palindrome

auto diffb = labs(bpalin - num);
auto diffh = labs(hpalin - num);
auto diffl = labs(lpalin - num);

auto nearest = (diffb < diffh) ?
(diffb < diffl) ? bpalin : lpalin :
(diffh < diffl) ? hpalin : lpalin;

ss << "nearest palindrome = "
<< nearest << endl;
return move(ss.str());
}(num));
} // end main


class Solution {
public String nearestPalindromic(String n) {
int order = (int) Math.pow(10, n.length()/2);
Long ans = Long.valueOf(new String(n));
Long noChange = mirror(ans);
Long larger = mirror((ans/order)*order + order+1);
Long smaller = mirror((ans/order)*order - 1 );
if ( noChange > ans) {
larger = (long) Math.min(noChange, larger);
} else if ( noChange < ans) {
smaller = (long) Math.max(noChange, smaller);
}
return String.valueOf( ans - smaller <= larger - ans ? smaller :larger) ;
}
Long mirror(Long ans) {
char a = String.valueOf(ans).toCharArray();
int i = 0;
int j = a.length-1;
while (i < j) {
a[j--] = a[i++];
}
return Long.valueOf(new String(a));
}


}


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.