Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Find the Closest Palindrome

Last Updated on April 6, 2022 by Ria Pathak

Strings

Hard

### Problem Statement (Simplified):

For given numbers we have to print the nearest anagram to it if two numbers are equidistant and anagram to the given number, print out the smallest. If the number is a palindrome itself, print its nearest palindrome.

See original problem statement here

#### Test Case

``````    Input:
3
6
127
121

Output:
5
131
111

Explanation:
Case-1:
5 is the nearest palindrome for 6.

Case-2:
127 has 121 and 131 as palindrome near to it. 131 is nearest to 127, so 131 is our answer.

Case-3:
121 has 111 and 131 as palindrome near to it. Both are equidistant to it. So we print the smallest one. Hence, 111 is our answer.``````

### Solving Approach :

For checking out the nearest palindrome, we check different cases.

• `Case -1:` If the number is a single digit, it answers will be one less to it.
• `Case -2:` If the number contains only 9’s at every place, the answer will be the number+2 always.
• `Case -3 :` If number is in form of `1000..{0,1}`, for example 10, 101, 100,1001 etc. The nearest palindromic number will be `n-1` times 9 where `n` is the length of number. For example `1001`‘s nearest palindrome is `999`.
• `Case -4:` If the number is not a palindrome, and does not come in the above-mentioned cases, then we print out the first half of number as the second half, so `abcdef` is printed as `abccba`.
• `Case -5:` If the number is a palindrome, we decrease the central digit by one in one case, and increase by 1 in second. On comparing whichever produces the smallest number we print that case as our result.

#### Example

Let’s discuss above cases with examples:

Case-1: If number is single is digit.
Lets assume number to be `5`, so we print `1` number less to it, so `4` is answer.

Case-2: If number contains only 9 in it.
Lets assume number to be `999`, so answer would be `number+` 2, Hence `1001` is our answer.

Case-3: If number contains 0 and 1 only, and number ends with 1.
Lets assume number to be `11`, so answer would be `number-` 2, Hence `9` is our answer.

Case-4: If number is not a palindrome.
Lets assume number to be `12344`, so answer would be `FirstHalf` + `middleNumber` + (`FirstHalf` `in` `reversed` `order`), Hence `12321` is our answer.

Case-5: If number is palindrome.
Lets assume two numbers here, if number is `12321`, middle digit is `3`, so we decrement middle digit by `1`. So, our answer is `12221`.

If number is `12121`, middle digit is `1`, so we increment middle digit by `1`. So, our answer is `12221`.

### Solutions

```#include <stdio.h>
#include<string.h>

void mirror(char n[]) {
for (int i = 0, j = strlen(n) - 1; i < j; i++, j--)
n[j] = n[i];
}

char* getUp(char raw[]) {
int mid = (strlen(raw) - 1) / 2;
while (raw[mid] == '9') {
raw[mid] = '0';
mid--;
}
if (mid == -1) {
char a[20] = "1";
strcat(a,raw);
strcpy(raw,a);
}
else
raw[mid] += 1;
mirror(raw);
return raw;
}

char* getLow(char raw[]) {
int mid = (strlen(raw) - 1) / 2;
while (raw[mid] == '0') {
raw[mid] = '9';
mid--;
}
if (mid == 0 && raw[mid] == '1' && strlen(raw) > 1) {
for (int i = 0; i < strlen(raw) - 1; i++)
raw[i] = '9';
raw[strlen(raw) - 1] = '\0';
} else {
raw[mid] -= 1;
mirror(raw);
}
return raw;
}

long long stoll(char a[]){
long long val=0, power=1;
for(int i=strlen(a)-1; i>=0; i--){
val += power*(a[i]-'0');
power*=10;
}
return val;
}

int main(){
int t;
scanf("%d",&t);
while(t--){
char n[20];
scanf("%s",n);
char raw[20], temp[20];
strcpy(raw,n);
strcpy(temp,raw);
mirror(n);
char up[20];
stoll(n) > stoll(raw) ? strcpy(up,n) : strcpy(up,getUp(raw));
strcpy(raw,temp);
char low[20];
stoll(n) < stoll(raw) ? strcpy(low,n) : strcpy(low,getLow(raw));
strcpy(raw,temp);
char str[20];
long long upN=stoll(up), nN=stoll(raw),lowN=stoll(low);
if(nN-lowN == upN-nN)
printf("%s\n",low);
else {
if(nN-lowN < upN-nN)
printf("%s\n",low);
else
printf("%s\n",up);
}
}

}

```
```#include <bits/stdc++.h>
using namespace std;
void mirror(string& n) {
for (int i = 0, j = n.size() - 1; i < j; i++, j--)
n[j] = n[i];
}
string getUp(string raw) {
int mid = (raw.size() - 1) / 2;
while (raw[mid] == '9') {
raw[mid] = '0';
mid--;
}
if (mid == -1) raw = "1" + raw;
else
raw[mid] += 1;
mirror(raw);
return raw;
}
string getLow(string raw) {
int mid = (raw.size() - 1) / 2;
while (raw[mid] == '0') {
raw[mid] = '9';
mid--;
}
if (mid == 0 && raw[mid] == '1' && raw.size() > 1) {
for (int i = 0; i < raw.size() - 1; i++)
raw[i] = '9';
raw[raw.size() - 1] = '\0';
} else {
raw[mid] -= 1;
mirror(raw);
}
return raw;
}

int main()
{
int t;
cin>>t;
while(t--){
string n;
cin>>n;
string raw = n;
mirror(n);
string up = stoll(n) > stoll(raw) ? n : getUp(raw);
string low = stoll(n) < stoll(raw) ? n : getLow(raw);
string str= stoll(up) - stoll(raw) >= stoll(raw) - stoll(low) ? low : up;
cout<<str<<endl;

}

}
```
```
import java.util.*;
import java.io.*;

public class Main{

static String mirror(String s){
StringBuilder temp  = new StringBuilder();
if(s.length()%2==0 ){
s = s.substring(0, s.length()/2 );
temp.append(s);
temp.reverse();
s += temp;
}
else{
s = s.substring(0, s.length()/2 + 1 );
temp.append(s.substring(0, s.length()-1));
temp.reverse();
s += temp;
}
return s;
}

static String getUp(String raw) {
int mid = (raw.length() - 1) / 2;
while (raw.charAt(mid) == '9') {
raw = raw.substring(0,mid) + '0' + raw.substring(mid+1);
mid--;
}
if (mid == -1) raw = "1" + raw;
else
raw = raw.substring(0,mid) + (char)((int)(raw.charAt(mid))+1) + raw.substring(mid+1);
// raw.charAt(mid) += 1;
raw  = mirror(raw);
return raw;
}

static String getLow(String raw) {
int mid = (raw.length() - 1) / 2;
while (raw.charAt(mid) == '0') {
raw = raw.substring(0,mid) + '9' + raw.substring(mid+1);
// raw.charAt(mid) = '9';
mid--;
}
if (mid == 0 && raw.charAt(mid) == '1' && raw.length() > 1) {
for (int i = 0; i < raw.length() - 1; i++)
raw = raw.substring(0,i) + '9' + raw.substring(i+1);
// raw[i] = '9';
raw = raw.substring(0, raw.length()-1);
} else {
raw = raw.substring(0,mid) + (char)((int)(raw.charAt(mid))-1) + raw.substring(mid+1);
raw = mirror(raw);
}
return raw;
}
public static void main(String args[]) throws IOException{

Scanner sc = new Scanner(System.in);
int test = sc.nextInt();

while(test-->0){
String n = sc.next();
String raw = n;
n = mirror(n);
String up = Long.parseLong(n) > Long.parseLong(raw) ? n : getUp(raw);
String low = Long.parseLong(n) < Long.parseLong(raw) ? n : getLow(raw);
String str= Long.parseLong(up) - Long.parseLong(raw) >= Long.parseLong(raw) - Long.parseLong(low) ? low : up;
System.out.println(str);
}
}
}
```

Space Complexity of this approach would be `O(N).`

[forminator_quiz id="777"]

This article tried to discuss the concepts of Strings. Hope this blog helps you understand and solve the problem. To practice more problems on Strings you can check out MYCODE | Competitive Programming