Last Updated on April 6, 2022 by Ria Pathak
Concepts Used
Strings
Difficulty Level
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 of1000..{0,1}, for example 10, 101, 100,1001 etc. The nearest palindromic number will ben-1times 9 wherenis the length of number. For example1001‘s nearest palindrome is999.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, soabcdefis printed asabccba.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