Palindrome Problem Statement Find the number of palindromes closest to the integer n.…
- User
Palindrome
Problem Statement
Find the number of palindromes closest to the integer n.
Note that the non-negative integer x is the number of palindromes, which means that the character string in which x is expressed in decimal notation and the character string in which it is inverted are equal. For example, 0,7,33,10301 is the number of palindromes, and 32,90,1010 is not the number of palindromes.
Constraints
- 1 ≤ n ≤ 10 ^ 4 Input
Input follows the following format. All given numbers are integers.
n
Output
Output the number of palindromes closest to n. If there are multiple such numbers, output the smallest one.
Examples
Input
13
Output
11
Input
7447
Output
7447
Input
106
Output
101
Assistant
We are asked: "Find the number of palindromes closest to the integer n." Actually: "Find the number of palindromes closest to the integer n." Means: given n (1 ≤ n ≤ 10000), we need to output the palindrome number that is closest to n. If there are two palindromes equally close (i.e., one lower and one higher both have same absolute difference), output the smallest one.
Constraints: n up to 10^4, so we could generate all palindromes up to maybe 20000 to be safe, but we can also compute directly.
Examples: n=13 -> output 11. Palindromes near 13: 11 (difference 2), 22 (difference 9). So closest is 11. If equal? e.g., n=10? Palindromes: 9 and 11 both diff 1 -> output smallest -> 9. Let's test: If n=10, 9 and 11 are both diff 1, smallest is 9. Similarly n=1? Palindromes: 1 itself is palindrome, so output 1 (closest). n=2? 2 is palindrome, output 2. n=3? output 3? Actually 3 is palindrome. n=4? 4. n=5? 5. n=6? 6. n=7? 7. n=8? 8. n=9? 9. So only interesting when n is not palindrome. But also numbers like 100: palindromes: 99 (diff 1) and 101 (diff 1) -> smallest is 99. So expected output 99? Let's see: example: n=106 -> output 101. So there 106 diff to 101 is 5, to 99 is 7, so 101.
Thus problem is straightforward.
Implementation: read n. Compute lower palindrome <= n and higher palindrome >= n. Then compare differences.
We could generate by checking numbers decreasing/increasing until palindrome found. Since n up to 10^4, worst-case scanning maybe few thousand steps, fine.
But better: for any given n, compute nearest palindrome. Could also generate all palindromes up to, say, 20000. Since n ≤ 10000, max maybe 19991? Actually the palindrome numbers could be bigger than n, but we only need closest. The distance from n to a palindrome > n might be up to maybe 10000? But to be safe we could search up to 20000. However we can compute directly by constructing palindromes from half.
But given constraints, easiest: for i from n downwards, check if i is palindrome; break when found. For j from n+1 upwards, check if palindrome; break. Then compare.
But careful: n itself might be palindrome, then output n directly.
Edge cases: n=1? i start from n downwards includes n, we'll find palindrome. So we can handle.
Complexity: O(D * L) where D is distance to next palindrome, L is number of digits. For n up to 10000, worst-case distance? For n around 10000, nearest palindrome? 9999 is palindrome? 9999 is palindrome? 9999 reversed is 9999, yes it's palindrome. So distance from 10000 to 9999 is 1, so lower palindrome exists. 10001 is palindrome? 10001 reversed is 10001, yes. So nearest are 9999 (diff 1) and 10001 (diff 1). So both diff 1, output smallest 9999. So scanning maybe from 10000 down to 9999 quickly. So it's fine.
Thus implement palindrome check: convert to string, compare to reversed.
We'll implement solve():
def is_palindrome(x): s = str(x) return s == s[::-1]
Read n.
if is_palindrome(n): print(n); return.
lower = n-1; while lower >= 0 and not is_palindrome(lower): lower -= 1
Since n>=1, lower will eventually hit 0? 0 is palindrome. So lower will be at least 0.
upper = n+1; while not is_palindrome(upper): upper += 1
Then diff_lower = n - lower, diff_upper = upper - n. if diff_lower < diff_upper: print(lower) elif diff_lower > diff_upper: print(upper) else: print(lower) # since smaller.
But careful: if lower < 0? Actually n≥1, and we will find palindrome at 0 only if n=1? For n=1, we handle earlier because palindrome, so lower won't be used. For n=2, lower scanning from 1 yields 1 which is palindrome, so fine. So lower won't be negative.
But we can ensure lower >= 0.
That's it.
But there is nuance: The problem statement says "Find the number of palindromes closest to the integer n." And "If there are multiple such numbers, output the smallest one." So our logic is correct.
Check examples: n=13: lower palindrome = 11, upper = 22, diff 2 vs 9 -> lower. Output 11. n=7447: it's palindrome -> output 7447. n=106: lower = 99? Actually check: start from 105 downwards? 105 not palindrome, 104 no, 103 no, 102 no, 101 yes -> lower = 101? Wait 101 is palindrome and less than 106, yes. Actually 101 < 106, yes. Then upper: 107,108,... 111? 111 is palindrome? 111 reversed 111, yes. But 111 - 106 = 5, while lower diff = 5 as well? 106-101=5. So both 101 and 111 have diff 5. According to rule, output smallest, which is 101. So our code would output lower (101) because diff equal and we choose lower. That matches example output: 101. So good.
Edge: n=10: lower=9, upper=11, diff both 1, output 9 (lower). That matches expectation.
Thus solution is simple.
But we must consider that n can be up to 10000, but we must also consider upper palindrome could be > 10000? For n=9999, upper palindrome is 10001 (since 10000 not palindrome). That's > 10000. But our scanning will eventually find it. The number of steps to reach 10001 from 10000 is 1 step? Actually from n=9999, we check if palindrome; it is, so output 9999. So upper not needed. For n=10000, lower: 9999 (palindrome) diff=1; upper: start from 10001? Actually we scan from 10001 upward: 10001 is palindrome, so upper=10001 diff=1. So both diff 1, output lower 9999. That's correct. So scanning upper from 10001 is fine.
Thus we can implement.
But caution: The problem statement might be originally in Japanese? It says "Find the number of palindromes closest to the integer n." Actually the phrase "the number of palindromes" means "the palindrome number". So it's fine.
Thus answer is simple.
But the instruction: "Write a solution in python" and "Only provide the final solution code inside the
pythonblock." So we just produce the final code.Let's include reading from standard input and writing to output.
Potential improvements: we could also directly generate palindromes for half-length to avoid scanning, but scanning is fine.
But note that the problem constraints are small, but we should be careful about infinite loops if we don't find palindrome? But there is always palindrome: numbers like 0,1,... So eventual.
We'll code:
import sys
def is_pal(x): s = str(x) return s == s[::-1]
def solve(): data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) if is_pal(n): print(n) return low = n-1 while not is_pal(low): low -= 1 high = n+1 while not is_pal(high): high += 1 if n - low < high - n: print(low) elif n - low > high - n: print(high) else: print(low) # because low < high
if name == "main": solve()
But check: When n=1, is_pal(1) true, prints 1. n=0 not allowed because n>=1. So fine.
But what about n=2? low=1, is_pal(1) true, high=3? 3 is palindrome, yes. diff: 2-1=1, 3-2=1, equal -> print low (1). But the correct answer? For n=2, is 2 itself palindrome? Yes, 2 is palindrome, so we would have printed 2 directly. Actually we check is_pal(n) first: 2 is palindrome, so prints 2. So correct.
Edge: n=10? is_pal(10) false, low=9 palindrome, high=11 palindrome, diff both 1, prints 9. Good.
Thus solution works.
But is there any case where low becomes negative? For n=1 we already handled. For n=2? low=1 positive. So fine.
Alright.
But the problem says n up to 10^4. So it's okay.
We can also implement by generating list of palindromes up to maybe 20000 and then binary search, but it's unnecessary.
Let's test with n=10000: low = 9999 (palindrome), high=10001 (palindrome). diff: 1 vs 1, print low 9999. That seems correct? But is 10000 closest to 9999 or 10001? Both diff 1, smallest is 9999. So output 9999. But is there any palindrome exactly 10000? No. So okay.
Now what about n=5? Already palindrome, prints 5.
Alright.
Thus final code as above.
But perhaps the original problem expects a method that directly constructs nearest palindrome. But scanning is simplest.
However, caution: The input format: n is given alone. So we read.
Thus final answer.
But the problem says: "Find the number of palindromes closest to the integer n." Could be misinterpreted as "find the count of palindromes that are closest"? No, it's clearly "the number" meaning the palindrome number. So fine.
Thus produce final code.
I'll include comments for clarity? But the answer expects just code.
I'll produce.
Note: In Python, reading from sys.stdin and converting to int, then implementing solve.
Given that the problem statement uses "number of palindromes", I'll just produce code.
Thus final. ```python
import sys
def is_palindrome(x: int) -> bool: s = str(x) return s == s[::-1]
def solve() -> None: data = sys.stdin.read().strip().split() if not data: return n = int(data[0])
# If n itself is a palindrome, output it directly. if is_palindrome(n): print(n) return # Find the first palindrome smaller than n. low = n - 1 while not is_palindrome(low): low -= 1 # Find the first palindrome larger than n. high = n + 1 while not is_palindrome(high): high += 1 # Choose the closest (or the smaller if ties). if n - low < high - n: print(low) elif n - low > high - n: print(high) else: print(low) # low < high when distances are equalif name == "main": solve()