Find the Closest Palindrome

This page explains Java solution to problem Find the Closest Palindrome using String data structure.

Problem Statement

Given an integer n, find the closest integer (not including itself), which is a palindrome.

The 'closest' is defined as absolute difference minimized between two integers.

Input: "123"
Output: "121"

Solution

package com.vc.hard;

import java.util.HashSet;

class FindClosestPalindrome {
    public String nearestPalindromic(String n) {
        int len = n.length();

        int middleIndex = len % 2 == 0 ? len / 2 - 1: len / 2;
        long prefix = Long.parseLong(n.substring(0, middleIndex + 1));

        HashSet<Long> candidates = new HashSet<>();
        candidates.add(helper(prefix, len % 2 == 1));
        candidates.add(helper(prefix + 1,  len % 2 == 1));
        candidates.add(helper(prefix - 1,  len % 2 == 1));
        candidates.add((long)Math.pow(10, len - 1) - 1);
        candidates.add((long)Math.pow(10, len) + 1);

        long diff = Long.MAX_VALUE;
        long res = Long.MAX_VALUE;
        long number = Long.parseLong(n);
        for(long candidate: candidates) {
            if(candidate == number) continue;
            else {
                if(Math.abs(number - candidate) < diff) {
                    diff = Math.abs(number - candidate);
                    res = candidate;
                }
                else if(Math.abs(number - candidate) == diff) {
                    res = Math.min(candidate, res);
                }
            }
        }
        return String.valueOf(res);
    }

    private long helper(long left, boolean isLengthOdd) {
        long res = left;
        if(isLengthOdd) left = left / 10;
        while(left > 0) {
            res *= 10;
            res += left % 10;
            left /= 10;
        }
        return res;
    }
}

Time Complexity

O(L) Where
L is length of input number

Space Complexity

O(1)