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
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
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
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
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
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
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());
}
}
}
Reference
