C# Lógica Pura— Resolução LeetCode 564 Find the Closest Palindrome

Olá pessoal!

Continuando com a ideia de resolver alguns desafios de código para compartilhar e exercitar alguma área do conhecimento, hoje vamos falar sobre um desafio de pura lógica que encontrei na mesma plataforma que mencionei no artigo anterior, Leetcode.

O desafio é o 564. Find the Closest Palindrome, detalharei o problema abaixo.

Problema

Dado um inteiro n, descubra o inteiro mais próximo que seja um palíndromo, não incluindo n. O número mais próximo é o que tem a menor diferença absoluta.

Número palíndromo é aquele que lendo em qualquer um dos dois sentidos o valor é o mesmo, por exemplo:

Número Palíndromo

O número 12521 tem o mesmo valor lendo da esquerda para a direita e da direita para a esquema.

A plataforma cita como exemplo: dado uma entrada “123" a saída do programa deve ser “121”.

São inclusas duas regras adicionais ao problema:

• n é um inteiro positivo representado por uma string, cujo tamanho não excede 18 posições;
• Se os palíndromos encontrados tiverem a mesma diferença para n, deve ser retornado o de menor valor.

Solução

Sendo sincero, demorei algumas horas para identificar a melhor forma de localizar o número palíndromo a frente ou a trás. De início pensei em ir incrementando/decrementando uma unidade por vez e testando se um número era palíndromo, mas isso geraria um esforço considerável.

Após algum tempo refletindo e visualizando um número palíndromo, vi que deveria ir ajustando o número, iniciando pela unidade até a potência do meio, para encontrar o palíndromo. Eu sei, a explicação não ajudou muito, mas vou tentar ser mais claro.

Dado o número 37576, o processo para encontrar o palíndromo a frente seria:

1. Visualize o número como um array, no qual o índice do array corresponde a potência de 10:

2. Primeiro devemos ajustar a posição 0 com a posição 4, portando devemos somar 7, pois 6 + 7 = 13, ficando 3 unidades e também incrementando uma dezena. O número após esse ajuste fica:

3. Agora devemos ajusta a posição 1 com a 3, só que na posição 1 devemos somar dezenas e não unidades, portando devemos somar 90, ficando:

4. Chegamos ao palíndromo a frente, 37673, com 2 operações. Os ajustes devem ser realizados até o meio do array, ou seja, “Array.Length / 2”.

Como implementei isso?

Primeiro criei uma função para determinar se um número é palíndromo. Esta função converte o número em string, e compara a posição 0 com a última, a posição 1 com a penúltima, e assim por diante até o meio do array (Length / 2). Se encontrar números diferentes ele retorna os dois números da comparação e a potência relacionada:

public static class NumericOperation
{
   public static NumericOperationResult IsPalindromic(long num)
   {
      var numa = num.ToString();
      var lastIndex = numa.Length - 1;
      var pow = 0;
      for (int i = 0; i < numa.Length / 2; i++)
      {
         if(numa[i] != numa[lastIndex - i])
         {
            return new NumericOperationResult() { IsPalindromic = false, DiferentIndex = pow, NumberDiffA = CharToLong(numa[lastIndex - i]), NumberDiffB = CharToLong(numa[i])  };
         
         }
        
         pow++;
      }
      return new NumericOperationResult() { IsPalindromic = true, DiferentIndex = -1 };
   }
}
public class NumericOperationResult
{
   // True se palíndromo palindromin   
   public bool IsPalindromic { get; set; }
   //Potência de 10 da posição com a diferença
   public int DiferentIndex { get; set; } 
   //Número da diferença A. No caso do primeiro ajuste de 37576, é 3
   public long NumberDiffA { get; set; }
   //Número da diferença B. No caso do primeiro ajuste de 37576, é 6
   public long NumberDiffB  { get; set; }
}

A função acima que determina se um número é palíndromo, IsPalindromic, é utilizada por uma outra função chamada FindNextPalindromic, que utiliza a potência de retorno, caso não seja palíndromo, para ir realizando o ajuste do número até encontrar o palíndromo.

public long FindNextPalindromic(long number)
{
   number++;
   while (true)
   {
      var operationResult = NumericOperation.IsPalindromic(number);
      
      if (operationResult.IsPalindromic)
         return number;
      long diff;
      if (operationResult.NumberDiffA > operationResult.NumberDiffB)
         diff = (operationResult.NumberDiffB + 10) - operationResult.NumberDiffA;
      
      else
         diff = operationResult.NumberDiffB - operationResult.NumberDiffA;
      number += (diff * Pow(10, operationResult.DiferentIndex));
   }
}

A função que faz a busca do palíndromo a trás é bem semelhante a FindNextPalindromic, só que ao invés de ir ajustando realizando soma, esta função ajusta realizando subtração. O processo é praticamente o mesmo, veja abaixo:

public long FindPreviousPalindromic(long number)
{
   number--;
   if (number <= 0)
      return 0;
   while (true)
   {
      var operationResult = NumericOperation.IsPalindromic(number);
      
      if (operationResult.IsPalindromic)
         return number;
      long diff;
      if (operationResult.NumberDiffA > operationResult.NumberDiffB)
         diff = operationResult.NumberDiffA - operationResult.NumberDiffB;
      else if (operationResult.DiferentIndex == 0)
         diff = 1;
      else
         diff = (operationResult.NumberDiffA + 10) - operationResult.NumberDiffB;
      number = number - (diff * Pow(10, operationResult.DiferentIndex));
      }
}

As três funções citadas acima são utilizadas para localizar o palíndromo a frente e a trás, e após é retornar o de menor diferença.

O que você achou da lógica implantada? Faria diferente? Fique a vontade para criticar a lógica adotada e também se tiver outro meio de chegar ao mesmo resultado compartilhe conosco ;)

O código completo esta disponível em meu GitHub.

Até o próximo problema!