Il mio codice è efficiente per scoprire il prossimo palindromo dato un numero intero positivo?

Question

Dichiarazione di problema: per un dato numero positivo, devo scoprire il palindromo immediatamente successivo. Ad esempio:

For 808, output:818 
2133, output:2222 

Voglio sapere se il mio codice è efficiente e quanto è efficiente? È un buon modo per risolvere il problema?

Spiegazione logica: ho impostato i nella posizione più a sinistra del numero, j nella posizione più a destra e sto praticamente confrontando i 2 numeri. Assegno sempre num[j]=num[i] e tengo traccia se il numero diventa maggiore del valore originale, o inferiore o uguale. Alla fine, ovvero: j-i==1 or j==i, a seconda del numero di cifre pari o dispari del numero, vedo se il numero è diventato maggiore o meno, prendendo una decisione di conseguenza.

MODIFICA: il numero può essere lungo fino a 100.000 cifre! .. Questo faceva parte della dichiarazione del problema, quindi sto cercando di evitare i metodi di forza bruta.

int LeftNineIndex = 0, RightNineIndex = 0; 
bool NumberLesser = false, NumberGreater = false; 
string number = Console.ReadLine(); 
char[] num = number.ToCharArray(); 
int i, j, x, y; 
for (i = 0, j = num.Length - 1; i <= j; i++, j--) 
{ 
     char m; 
     Int32.TryParse(num[i].ToString(),out x); 
     Int32.TryParse(num[j].ToString(), out y); 
     if (x > y) 
     { 
      NumberGreater = true; 
      NumberLesser = false; 
     } 
     else if (x < y) 
     { 
      if (j - i == 1) 
      { 
       NumberGreater = true; 
       NumberLesser = false; 
       x = x + 1; 
       Char.TryParse(x.ToString(), out m); 
       num[i] = m; 
      } 
      else 
      { 
       NumberGreater = false; 
       NumberLesser = true; 
      }    
    } 

    if ((j == i && NumberGreater == false) || (j - i == 1 && x == y && NumberGreater == false)) 
    { 
      if (x != 9) // if the number is 9, then i can't add 1 to it 
      { 
       x = x + 1; 
       Char.TryParse(x.ToString(), out m); 
       num[i] = m; 
      } 
      else 
      { 
       if (num.Length != 1) 
       { 
        Int32.TryParse(num[LeftNineIndex].ToString(), out x); 
        Int32.TryParse(num[RightNineIndex].ToString(), out y); 
        x = x + 1; 
        Char.TryParse(x.ToString(), out m); 
        num[LeftNineIndex] = m; 
        num[RightNineIndex] = m; 
       } 
       else 
       { 
        // user has entered just '9', in which case I've hard-coded 
        Console.WriteLine("11"); 
       } 
      } 
    } 
    num[j] = num[i]; 
    if (x != 9) //gives us the index of the number closest to the middle, which is not 9 
    { 
      LeftNineIndex = i; 
      RightNineIndex = j; 
    } 
} 
Console.WriteLine(num); 

Answer 1

E 'relativamente semplice per trovare il prossimo palindromo in tempo costante:

• Spalato l'ingresso in due metà (prima metà più grandi se la lunghezza è dispari)
• Ora per la prossima palindromo ci sono due candidati:
  1. mantenere il primo tempo, e fissare la seconda metà
  2. Incremento della prima metà di 1, e fissare la seconda metà
• Scegliere il primo candidato se è maggiore dell'input, altrimenti scegliere il secondo candidato.

Il tipo BigInteger è utile per attuare questo:

Questo approccio ha un costo lineare nella lunghezza dell'input, cioè è logaritmica nella dimensione del numero.

public static BigInteger NextPalindrome(BigInteger input) 
{ 
    string firstHalf=input.ToString().Substring(0,(input.ToString().Length+1)/2); 
    string incrementedFirstHalf=(BigInteger.Parse(firstHalf)+1).ToString(); 
    var candidates=new List<string>(); 
    candidates.Add(firstHalf+new String(firstHalf.Reverse().ToArray())); 
    candidates.Add(firstHalf+new String(firstHalf.Reverse().Skip(1).ToArray())); 
    candidates.Add(incrementedFirstHalf+new String(incrementedFirstHalf.Reverse().ToArray())); 
    candidates.Add(incrementedFirstHalf+new String(incrementedFirstHalf.Reverse().Skip(1).ToArray())); 
    candidates.Add("1"+new String('0',input.ToString().Length-1)+"1"); 
    return candidates.Select(s=>BigInteger.Parse(s)) 
       .Where(i=>i>input) 
       .OrderBy(i=>i) 
       .First(); 
} 

testato per funzionare con tutti i numeri interi positivi al di sotto 100000 confrontando con l'implementazione nativa.

Il quinto caso è facile da perdere. Se il numero è composto da tutti gli 9 s, l'incremento del primo semestre modifica la lunghezza e richiede una gestione aggiuntiva se la lunghezza corrente è dispari (9, 999, ...).

Answer 2

Ecco come l'ho fatto. Sembra funzionare.

 private int FindNextPaladindrone(int value) 
    { 
     int result = 0; 
     bool found = false; 

     while (!found) 
     { 
      value++; 
      found = IsPalindrone(value); 
      if (found) 
       result = value; 
     } 

     return result; 
    } 

    private bool IsPalindrone(int number) 
    { 
     string numberString = number.ToString(); 
     int backIndex; 

     bool same = true; 
     for (int i = 0; i < numberString.Length; i++) 
     { 
      backIndex = numberString.Length - (i + 1); 
      if (i == backIndex || backIndex < i) 
       break; 
      else 
      { 
       if (numberString[i] != numberString[backIndex]) 
       { 
        same = false; 
        break; 
       } 
      } 
     } 
     return same; 
    }