# Find the closest palindromic number

Given a number N, output/return X so that N+X is a palindrome, where |X| has to be as small as possible.

Palindrome: A number is a palindrome, if its sequence of digits is the same when reading them from left to right as when reading from right to left.
`95359` and `6548456` are symmetric, `123` and `2424` are not. Numbers with leading zeros such as `020` are not a palindrome.

Input is a positive integer smaller than 1015. Read it from stdin, as a method-parameter, whatever.

Output has to be an integer (positive or negative) and ought to be 0 if the input is already a palindrom. You may write your output to stdout, return it from a function or whatever you like. If there are 2 numbers (e.g. `2` and `-2`) that satisfy the requirements, output only one of them.

Examples:

``````Input             Output
3                 0
234               -2
1299931           -10
126               5 or -5 (only one of them)
``````
-
The common term is palindrome, not symmetrical number. – isaacg Aug 27 '14 at 13:34
Presumably if a number is halfway between the two nearest palindromes, either is an acceptable output? E.g. for `N=10` the output can be `X=-1` or `X=1`? – Peter Taylor Aug 27 '14 at 13:45
For what it's worth, the hasty editing which has left two answers which don't comply with the edited spec could have been avoided by using the Sandbox for Proposed Challenges. – Peter Taylor Aug 27 '14 at 13:49
@Moop You can find a palindrome pretty quickly, since at worst you can change half the digits to match. That doesn't always give the smallest change, but it's an easy upper bound. – Geobits Aug 27 '14 at 18:35
Since output says it "may be 0" if the number is already a palindrome, that means that X may be > 0 even if it would otherwise equal 0? Or should that be "ought to be 0"? – guifa Aug 28 '14 at 3:50

# Pyth, 26 20

``````Lnb_bWP`+QZ=Z-g0ZZ)Z
``````

Updated to meet the new rules.

The program runs in an infinite loop which tests every possible increment, in the order 0, -1, 1, -2, -2 ...

Explanation:

``````Q=eval(input())     implicit
Z=0                 implicit
Lnb_b               def P(b): return b != rev(b)
WP`+QZ              while P(repr(Q+Z)):
=Z-g0ZZ             Z=(0>=Z)-Z
)                   <end while>
Z                   print(Z)
``````

Example run:

``````python3 pyth.py programs/palin.pyth <<< 965376457643450
-2969881
``````

This took 23 seconds.

Bonus solution, same character count:

``````Wn`+QZ_`+QZ=Z-g0ZZ)Z
``````
-
Just to let you know, the rules changed to finding the nearest palindrome (in either direction). But I guess since you posted before that rule change there's no obligation for you to fix it. – Martin Ender Aug 27 '14 at 14:12
Might it save chars to loop Z through `[0, 1, -1, 2, -2, ...]` by an update `Z=-Z+(Z<0)`? – xnor Aug 27 '14 at 20:37
Yep - I thought of that independently. – isaacg Aug 27 '14 at 23:31
@xnor Added. Filler. – isaacg Aug 27 '14 at 23:36
Ok, cool. Have you also looked into putting the negation of the condition into the while? And maybe saving a repr by applying it to the input to P? – xnor Aug 27 '14 at 23:40

# Ruby, 111 84 bytes

``````i=\$*[j=-1].to_i
r=->j{s=(i+j).to_s
abort(j.to_s)if s==s.reverse}
loop{r[j+=1]
r[-j]}
``````

Takes the number as its only command-line argument.

-
@Manu Thanks didn't know that one! My submission works as far as I can tell. – Martin Ender Aug 27 '14 at 14:01

# CJam, 3429 25 bytes

``````q~:I!{:R1<R-RI+`_W%=!}g;R
``````

Try it online.

### Examples

``````\$ cjam palfind.cjam <<< 120; echo
1
\$ cjam palfind.cjam <<< 121; echo
0
\$ cjam palfind.cjam <<< 122; echo
-1
``````

### How it works

``````q~:I    " Read from STDIN, evaluate and save the result in “I”.                           ";
!       " Compute the logical NOT (0 since the integer is positive).                      ";
{       "                                                                                 ";
:R    " Save the topmost integer in “R”.                                                ";
1<R-  " Compute (R < 1) - R. This produces the sequence 0 → 1 → -1 → 2 → -2 → … .       ";
RI+   " Push I + R.                                                                     ";
`_    " Cast to string and push a copy.                                                 ";
W%=!  " Check if the reversed copy matches the original.                                ";
}g      " If it doesn't, repeat the loop.                                                 ";
;R      " Discard the integer on the stack and push “R”.                                  ";
``````
-

``````f n=[x-n|x<-[0..]>>= \v->[n+v,n-v],show x==(reverse.show)x]!!0
``````

Save it to a file named `golf.hs` and then test it with ghci:

``````*Main> :l golf
[1 of 1] Compiling Main             ( golf.hs, interpreted )
*Main> map f [1000..1050]
[-1,0,-1,-2,-3,-4,-5,-6,-7,-8,-9,-10,-11,-12,-13,-14,-15,-16,-17,-18,-19,-20,-21,-22,-23,-24,-25,-26,-27,-28,-29,-30,-31,-32,-33,-34,-35,-36,-37,-38,-39,-40,-41,-42,-43,-44,-45,-46,-47,-48,-49]
*Main>
``````
-
how about writing `x<-[0..]>>=(\v->[n+v,n-v])` ? It is shorter and it makes it a one-liner – proud haskeller Aug 28 '14 at 7:43
@proudhaskeller Thanks! Very elegant trick with the list monad. – Ray Aug 28 '14 at 7:50

## Perl 5, 938988877563 44

``````\$/=(\$/<1)-\$/while\$_+\$/-reverse\$_+\$/;\$_=\$/+0
``````

Ungolfed:

``````while(\$input + \$adjustment - reverse(\$input + \$adjustment)) {
}
\$input = \$adjustment + 0;  ## gives 0 if \$adj is undefined (when \$input is a palindrome)
print \$input;  ## implicit
``````

Thanks to Dennis's suggestions, got it down to 43 + `-p` = 44

-
1. `-\$a` is shorter than `\$a*-1`. 2. If you use `(\$a<1)`, there's no need for `? :\$a++`. 3. If you use the `-p` switch, `\$_=<>` and `print\$_` is implicit, so you can drop the first statement and change the last to `\$_=\$a+0`. – Dennis Aug 28 '14 at 21:55
@Dennis Nice finds. This is only my second attempt at code golf, so appreciate the advice! – guifa Aug 28 '14 at 22:02
It's customary to count the `-p` switch as one extra byte, but you can get it back by using `(\$a<1)-\$a` instead of `-\$a+(\$a<1)`. – Dennis Aug 28 '14 at 22:52
@Dennis I though about using that method based on your answer above, but the gain gets lost because it requires a space before `while` – guifa Aug 28 '14 at 22:56
If you use `\$/` instead of `\$a`, it will work. – Dennis Aug 28 '14 at 23:01

# Python 2.7, 98, 81

Creates a palindrome from the input number, then subtracts that from the input to find the delta.

``````def f(n):
m=map(int,str(n));l=len(m)/2;m[-l:]=m[l-1::-1];return int(`m`[1::3])-n
``````

usage:

``````print f(3)          # 0
print f(234)        # -2
print f(2342)       # -10
print f(129931)     # -10
print f(100000)     # 1
``````

ungolfed and annotated:

``````def f(n):                      # take a integer n
m=map(int,str(n));         # convert n into array of ints
l=len(m)/2;                # get half the length of the array of ints
m[-l:]=m[l-1::-1];         # replace the last elements with the first elements reversed
return int(`m`[1::3])-n    # convert array of ints backinto single int and subtract the original number to find the delta
``````
-
This doesn't give the smallest delta. `f(19) = -8` (palindrome `11`), where it should be `+3` to make `22`. – Geobits Aug 27 '14 at 18:31
@Geobits Yes, the 10-100 values will give me a problem with this approach – Moop Aug 27 '14 at 18:47
It's not just those. Similarly, 199999 gives -8 instead of 3, 9911 gives 88 instead of -22. Just reversing the first digits doesn't work to get the smallest delta in a lot of cases. – Geobits Aug 27 '14 at 18:52
well i wouldn't say a lot of cases, i bet 99.9% of cases it works for. But yes, it needs to work for 100% of cases – Moop Aug 27 '14 at 18:55
@Geobits. Sure, so 27% error rate there. But when you get to the 100000000s the error rate drops considerably. It would be interesting to calculate the actual error rate. – Moop Aug 27 '14 at 19:08

# Java : 127 109

Basic iteration, checking both negative and positive before moving to the next candidate.

``````int p(long n){int i=0;for(;!(n+i+"").equals(new StringBuilder(n+i+"").reverse()+"");i=i<1?-i+1:-i);return i;}
``````

For input `123456789012345`, it returns `-1358024`, to equal palindrome `123456787654321`.

Line breaks:

``````int p(long n){
int i=0;
for(;!(n+i+"").equals(new StringBuilder(n+i+"").reverse()+"");i=i<1?-i+1:-i);
return i;
}
``````
-
Does `n+i+""` work and save the brackets? I think that the precedence should be correct. – Peter Taylor Aug 27 '14 at 14:45
@PeterTaylor Yep, and got another few from `toString()`. Thanks :) – Geobits Aug 27 '14 at 14:53
Can I steal that sweet `i=i<1?-i+1:-i`? I shall call it "indecrement". – Jacob Aug 28 '14 at 9:19
@Jacob Go for it ;) – Geobits Aug 28 '14 at 12:32

# Clojure, 92

Takes the first from a lazy for-sequence that works from 0 out and only includes values that make palindromes:

``````(defn p[x](first(for[i(range)j[1 -1]k[(* i j)]s[(str(+ x k))]:when(=(seq s)(reverse s))]k)))
``````

REPL-LPER session:

``````golf-flog> (p 3)
0
golf-flog> (p 10)
1
golf-flog> (p 234)
-2
golf-flog> (p 1299931)
-10
golf-flog> (p (bigint 1e15))
1
``````
-

# JavaScript, 175136 117

Straightforward. `p` returns true if a given number is palindrome, `f` searches the nearest.

EDIT: I also golfed it a little bit more thanks to the sweet "indecrement" trick by Geobits in the Java answer here.

``````p=function(n){return (s=''+n).split('').reverse().join('')==s}
f=function(n){for(i=0;!p(n+i);i=i<1?-i+1:-i);return i}
``````

Usage:

``````f(3)
f(234)
f(1299931)
``````
-
104 in ES6: `p=n=>[...s=''+n].reverse().join('')==s f=n=>{r=t=0;while(!(p(n+r++)||p(n+t--)));return p(n+r-1)?r-1:t+1}` :) – William Barbosa Aug 27 '14 at 19:09
I bet it is. `function` and `return` are terribly long reserved-words... – Jacob Aug 27 '14 at 19:12

## Groovy - 131111 107 chars

Golfed:

``````n=args[0] as long;a=n;b=n;f={if("\$it"=="\$it".reverse()){println it-n;System.exit 0}};while(1){f a++;f b--}
``````

sample runs:

``````bash-2.02\$ groovy P.groovy  0
0
bash-2.02\$ groovy P.groovy  234
-2
bash-2.02\$ groovy P.groovy  1299931
-10
bash-2.02\$ groovy P.groovy  123456789012345
-1358024
``````

Ungolfed:

``````n=args[0] as long
a=n
b=n
f={ if("\$it"=="\$it".reverse()) {
println it-n
System.exit 0
}
}

while(1) {
f a++
f b--
}
``````
-

## C++ 289

Function P checks for palindromes using `<algorithm>` method.

Ungolfed:

``````bool P(int32_t i)
{
string a,b;
stringstream ss;
ss<<i;
ss>>a;
b=a;
reverse_copy(b.begin(),b.end(),b.begin());
int k=a.compare(b);
return (k==0);
}
int main()
{
int32_t n; cin>>n;
int32_t x=0,y=n,z=n,ans=x;
while(1)
{
if(P(y)){ans=x; break;}
if(P(z)){ans=-1*x; break;}
x++;
y+=x;
z-=x;
}
cout<<ans<<endl;
return 0;
}
``````
-
It will be shorter to put everything on one line. – cat Jun 24 at 13:01

## Mathematica 75

Probably can be golfed more..

``````p = (j=0; b=#; While[a=IntegerDigits[b]; b += ++j(-1)^j; a!=Reverse[a]]; #-b+(-1)^j) &
``````

Spaces not counted and not needed.

-

# J - 49 char

A function mapping integers to integers.

``````((0{g#f)>:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0)
``````

Here's how you might build to this result, in three parts. This is the display of the J REPL: indented lines are user input and outdented ones are REPL output. And yes, J spells the negative sign with an underscore `_`.

``````   236 (_1 1*]) 4                          NB. -ve and +ve of right arg
_4 4
236 (f=._1 1*]) 4                       NB. name it f
_4 4
236 (+f=._1 1*]) 4                      NB. add left to each
232 240
236 (":@+f=._1 1*]) 4                   NB. conv each to string
232
240
236 ((-:|.)@":@+f=._1 1*]) 4            NB. palindrome? on each
1 0
236 (g=.(-:|.)@":@+f=._1 1*]) 4         NB. name it g
1 0
236 (+:/@g=.(-:|.)@":@+f=._1 1*]) 4     NB. logical NOR (result 1 if both=0)
0
palin =: (+:/@g=.(-:|.)@":@+f=._1 1*])

236 (>:@]) 0                            NB. increment right
1
236 (>:@]^:2) 0                         NB. functional power
2
236 (>:@]^:(236 palin 3)) 3             NB. power 1 if no palindromes
4
236 (>:@]^:(236 palin 4)) 4             NB. power 0 if has palindrome
4
236 (>:@]^:palin) 4                     NB. syntactic sugar
4
4
(>:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0) 236    NB. bind 0
4
delta =: >:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0

((f) delta) 236       NB. f=: -ve and +ve
_4 4
((g) delta) 236       NB. g=: which are palindromes
1 0
((g#f) delta) 236     NB. select the palindromes
_4
((g#f) delta) 126     NB. what if both are equal?
_5 5
((0{g#f) delta) 126   NB. take the first element
_5
((0{g#f)>:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0) 236   NB. it works!
_4
``````

Examples:

``````   pal =: ((0{g#f)>:@]^:(+:/@g=.(-:|.)@":@+f=._1 1*])^:_&0)
pal 3
0
pal every 234 1299931 126
_2 _10 _5
pal 2424
18
2424 + pal 2424
2442
``````

You can also make the golf prefer the positive solution over the negative when they're equal, by changing `_1 1` to `1 _1`.

-

# CoffeeScript: 73

``````(x)->(x+="")[0...(y=x.length/2)]+x[0...-y].split("").reverse().join("")-x
``````

Explanation: This takes advantage of the fact that if we have a number of odd length (say 1234567), `x.slice(0, y)` won't include the middle digit but `x.slice(0, -y)` will. JavaScript's `slice` probably shouldn't work this way, but it does.

I was expecting CoffeeScript/JavaScript to have a better way to reverse a string, but the split/reverse/join method seems to be all there is.

-

# Python 2 - 76

``````i=input()
print sorted([r-i for r in range(2*i)if`r`==`r`[::-1]],key=abs)[0]
``````

Gets the input number and generates a list of the differences between the input and every number between `0` and `2*i` only if the number is palindromic.

It then sorts the list by absolute value and prints the first element.

-
I don't think range(2*i) will work for large inputs. – Moop Aug 27 '14 at 20:13
You can use `min` with a keyword argument rather than sorting. – xnor Aug 27 '14 at 21:00
To use ranges that long, you need to switch to xrange, which is a generator, and min, which short-circuits, to avoid overrunning your memory. – isaacg Aug 28 '14 at 1:56

Python, 109

``````def q(x,z):
r=lambda s:int(str(s)[::-1])
if x+z==r(x+z):return z
if x-z==r(x-z):return -z
return q(x,z+1)
``````
-
this throws an error when running (maximum recursion depth exceeded) – Moop Aug 27 '14 at 17:47
That's not an error in my code. It will exceed maximum recursion depth on a massive number, but it works on decently sized numbers. As there was no maximum test case in the specs, this should still be considered a valid solution. – Batman Aug 27 '14 at 18:10
The number `123456789` causes it to fail, well below the 10^15 limit posted in the question. – Moop Aug 27 '14 at 18:13
You could easily turn the recursion into a loop and avoid this issue altogether – Moop Aug 27 '14 at 18:15
Running this in the Stackless Python implementation should avoid the recursion depth issue. – xnor Aug 27 '14 at 19:26