Introduction

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input:
2
808
2133

Output:
818
2222

Examples

Approach

We follow the computations from the string perspective on the given number, let's discuss a few cases,

Even Length Digit

Case 1:
When the reversed left half is greater than the right half, we copy the first half to the second half.

Example 1:
283349
-> When the reversed left half is less than the right half, 382 > 349

283382
We copy the left half to the right half

Even Digit Length Case: Reversed Left half is greater than the Right Half

Case 2:
When the reversed left half is less than the right half, we increment the left half with one (with carry if required)

Example 1:
283849
-> When the reversed left half is less than the right half, 382 < 849

284482
We increment the left half with one

Even Digit Length Case: Reversed Left half is less than the Right Half

2. Odd Length Digit

Case 1:
When the reversed left half is greater than the right half excluding the middle element, we copy the first half to the second half.

Example 1:
28749
-> Reversed left half is greater than the right half excluding the middle element, 82 > 49

We copy the first half to the second half
28782

Example 2:
283929349
-> Reversed left half is greater than the right half excluding the middle element, 9382 > 9349

We copy the first half to the second half
283929382

Odd Digit Length Case: Reversed Left half is greater than the Right Half

Case 2:
When the reversed left half is less than the right half excluding the middle digit inclusive of carry operation to left, we increment the left half with one including the middle element

Example 1:
23749
-> When the reversed left half is greater than the right half excluding the middle element, 32 < 49

23832
We increment the left half with one including the middle element and copy the first half to the right excluding the middle element


Example 2:
24983
-> Reversed left half is greater than the right half excluding the middle element, 42 < 83

25052
We increment the left half with one including the middle element inclusive of carry operation to left and copy the first half to the right excluding the middle element

Odd Digit Length Case: Reversed Left half is less than the Right Half

3. All 9s

We repeat the zeros with one length less than the number of 9s and appending with one on each side.

Example 1:
9999
-> All 9s, we count the number of digits and we create 1<0x(number 9s-1)>1

10001
We count four 9s and we add three zeros between two ones

All Nines Case

Code

In the below approach, we can use the BigInteger present in the System.Numerics namespace. It wasn't acceptable in the InterviewBit so I have coded the ParseAndIncrement method.

using System;
using System.Linq;

namespace Competitive
{
    internal class Program
    {
        public static void Main()
        {
            var t = int.Parse(Console.ReadLine() ?? "0");

            while (t-- > 0)
            {
                Console.WriteLine(Solve(Console.ReadLine()));
            }
        }
        private static string Solve(string a)
        {
            var n = a.Length;
            var isEven = n % 2 == 0;
            var center = n / 2;

            // Handle Nines
            var nineCount = a.Count(ch => ch == '9');
            var allNines = nineCount == n;
            if (allNines)
            {
                return "1" + new string('0', nineCount - 1) + "1";
            }

            // Handle Even case
            if (isEven)
            {
                var leftHalf = a.Substring(0, center);
                var reversedLeftHalf = new string(leftHalf.Reverse().ToArray());
                var rightHalf = a.Substring(center);
                if (string.Compare(reversedLeftHalf, rightHalf, StringComparison.Ordinal) > 0)
                {
                    return leftHalf + reversedLeftHalf;
                }

                // var left = BigInteger.Parse(leftHalf);
                // left++;
                var left = ParseAndIncrement(leftHalf);
                return left + new string(left.Reverse().ToArray());
            }
            else // Handle Odd case
            {
                var leftHalf = a.Substring(0, center);
                var middle = a.Substring(center, 1);
                var rightHalf = a.Substring(center + 1, center);
                var reversedLeftHalf = new string(leftHalf.Reverse().ToArray());
                if (string.Compare(reversedLeftHalf, rightHalf, StringComparison.Ordinal) > 0)
                {
                    return leftHalf + middle + reversedLeftHalf;
                }

                // var left = BigInteger.Parse(leftHalf + middle);
                // left++;
                var left = ParseAndIncrement(leftHalf + middle);
                leftHalf = left;
                return leftHalf + new string(leftHalf.Substring(0, center).Reverse().ToArray());
            }
        }
        private static string ParseAndIncrement(string s)
        {
            var n = s.Length;
            var carry = 0;
            var s2 = "";
            for (var i = n - 1; i > -1; i--)
            {
                var val = int.Parse(s[i].ToString());
                val += carry;
                if (i == n - 1)
                {
                    val += 1;
                }
                carry = val / 10;
                val = val % 10;
                s2 += val.ToString();
            }
            if (carry > 0)
            {
                s2 += carry.ToString();
            }
            return new string(s2.Reverse().ToArray());
        }
    }
}

C# Program