Find the Closest Palindrome

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 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 learn programming online and 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).

Previous post Maximize The Boxes
Next post Branches of Bytecode

Leave a Reply

Your email address will not be published. Required fields are marked *