Katkat
Back

Check palindrome number and next palindrome

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests your ability to manipulate digits of an integer to identify palindromes and efficiently construct the smallest palindrome greater than a given number.

Problem Statement

Given an integer n, write a function find_next_palindrome(n) that returns the smallest palindrome integer strictly greater than n. Assume n is a non-negative integer.

Requirements

  • You must handle cases where the next palindrome requires adding a digit (e.g., input 99, output 101).
  • Efficiency is important; avoid converting to strings if possible, or provide a solution that operates in O(d) time where d is the number of digits.

Examples

  1. find_next_palindrome(121) -> 131
  2. find_next_palindrome(99) -> 101
  3. find_next_palindrome(8) -> 9

Constraints

  • `0 int: pass

Hints

Hint 1

Consider splitting the number into two halves; the palindrome is primarily determined by mirroring the left half onto the right.

Hint 2

If mirroring the left half results in a number smaller than or equal to n, you need to increment the middle digit(s) of the left half and propagate any carries.

Hint 3

Special cases occur when the number consists entirely of 9s, in which case the next palindrome is always 1 followed by zeros and a 1 (e.g., 999 -> 1001).

Follow-up questions

  • How would your approach change if the input was provided as a very large string representing a number with 10,000 digits?
  • What is the time and space complexity of your solution, and can it be optimized further for memory?
  • How would you modify the function to find the *closest* palindrome, which could be either smaller or larger than the input?