When I run the below C# Code with the inline logic, I get the TLE. I had used the BigInteger
for incrementing the left side and also, created my custom parser but that didn’t help. This solution is passed in the InterviewBit website. Is it possible to solve the problem with the language? Thanks in advance for any inputs that result in closure.
using System;
using System.Linq;
// using System.Numerics;
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());
}
}
}