Largest Palindrome efficiency

Question

I have written an algorithm to find the largest palindrome under a given number, but I am sure my code loses efficiency by creating new arrays in every pass. I am currently learning about efficiency so I have the following question: Can anyone suggest a more efficient (faster) approach and explain why this approach is more efficient?

int number = 0;
int palindrome = 0;

for (int i = 1; i < 999999; i++)
{
    number = i;
    string s = number.ToString();
    char[] charArray = s.ToCharArray();
    char[] charArrayReversed = new char[charArray.Length];
    Array.Copy(charArray, charArrayReversed, charArray.Length);

    Array.Reverse(charArrayReversed);
    bool isEqual = Enumerable.SequenceEqual(charArray, charArrayReversed);
    if (isEqual)
        palindrome = number;
}


Console.Write(palindrome);
Console.ReadLine();

Answer 1

Take the first half of the digits then add the reverse (keeping the middle in mind for odd length values). Then check if this new value is smaller than the original. If so, we are done.
This is because the most significant digits are necessary for making the number as large as possible.

If the number we created is too large, we need to make it a bit smaller. To do this we'd like to shrink the middle if we can, since that's where we'll find the least significant digits. This has to account for the fact that if there is a single middle digit (odd length) it doesn't get mirrored, so in that case the code doesn't copy the entire half.

string Palindrome(string largest)
{ 
  int len = largest.Length;

  //Special case. This is the only case where the number of digits in the result is different.
  if (IsPowerOf10(Int32.Parse(largest)))
  {
    return new String('9', len - 1);
  }

  //This will keep the middle digit if it's odd lengthed.
  string firstHalf = largest.Substring(0, (len + 1) / 2);
  //This will drop the middle digit if it's odd lengthed, so that it's not repeated.
  string secondHalf = Reverse(firstHalf.Substring(0, len / 2));

  if (firstHalf + secondHalf > largest) //string concat then compare, not int operations.
  {
    firstHalf = (Int32.Parse(firstHalf) - 1).ToString();
  }

  return firstHalf + Reverse(firstHalf.Substring(0, len / 2);
}

public static string Reverse(string s)
{
    char[] charArray = s.ToCharArray();
    Array.Reverse(charArray);
    return new string(charArray);
}

public static bool IsPowerOf10(int i)
{
  i = i * 10; //for the case when i == 1
  while(i > 10) //keeping it above 10 will avoid things like 11/10 == 1 leading to wrong results.
  {
    i = i/10;
  }

  return i == 10;
}

Don't know if this compiles.

Answer 2

I'm sure there are other ways to improve it but here are a few quick points:

1. Start from the end and work your way back, that way once you've found one palindrome you're done!
2. You only have to check half of the digits for equality.
3. We can shave off some time by avoiding Array.Copy / Array.Reverse

Something like this:

var limit = ?
for (int i = limit; i > 0; i--)
{
    number = i;
    string s = number.ToString();
    char[] charArray = s.ToCharArray();

    bool isEqual = true;
    int halfLength = charArray.Length / 2; // will skip the middle digit
    int max = charArray.Length - 1;
    for(int j = 0; j < halfLength; j++)
    {
        if(charArray [j] != charArray[max - j])
        {
            isEqual = false;
            break;
        }
    }

    if (isEqual)
    {
        palindrome = number;
        break; // stop evaluating here
    }
}

Answer 3

Try this

    int number = 0;
    int palindrome = 0;

    for (int i = 99999998; i >0 ; i--)
    {
        number = i;
        string s = number.ToString();
        char[] charArray = s.ToCharArray();
        char[] charArrayReversed = new char[charArray.Length];
        Array.Copy(charArray, charArrayReversed, charArray.Length);

        Array.Reverse(charArrayReversed);
        bool isEqual = Enumerable.SequenceEqual(charArray, charArrayReversed);
        if (isEqual)
        {
            palindrome = number;
            break;
        }
    }


    Console.Write(palindrome);
    Console.ReadLine();

more than technical optimization I have done some logical optimization. Run the loop in reverse and break at the first palindrome!

Answer 4

There is no need to do it by brute-force approach, or even reduced version of brute-force. We can just cut the max value to half, handle odd and even digits logic and all special cases then it's done.

private static int MakePalindrome(int left, int? cen)
{
    string right = new string(left.ToString().Reverse().ToArray());
    string cenStr = cen.HasValue ? cen.ToString() : string.Empty;
    return int.Parse(left.ToString() + cenStr + right);
}

private static int MaxPalindrome(int maxValue)
{
    string digits = maxValue.ToString();
    if (digits.Length == 1) return maxValue;
    bool hasCen = digits.Length % 2 > 0;
    int left = int.Parse(digits.Substring(0, digits.Length / 2));
    int oLeft = left;
    int? cen = hasCen ? int.Parse(digits.Substring(digits.Length / 2, 1)) : (int?) null;
    int result = MakePalindrome(left, cen);
    if (result > maxValue)
    {
        if (hasCen)
        {
            cen--;
            if (cen < 0)
            {
                cen = 9;
                left--;
            }
        }
        else
        {
            left--;
        }

        if (left == 0 || left.ToString().Length < oLeft.ToString().Length)
        {
            result = int.Parse(new string('9', digits.Length - 1));
        }
        else
        {
            result = MakePalindrome(left, cen);
        }
    }
    return result;
}

Here is the code to test my logic:

    int lastPalindrome = 0;
    for (int i = 0; i < 10000; i++)
    {
        int newPalindrome = MaxPalindrome(i);
        if (lastPalindrome == 0) lastPalindrome = newPalindrome;
        Console.WriteLine("{0}/{1}", i, newPalindrome);
        if (lastPalindrome != newPalindrome)
        {
            if (i != newPalindrome) {
                Console.WriteLine("***{0}/{1}", i, newPalindrome); 
                throw new InvalidProgramException("Incorrect palindrome");
            }
            lastPalindrome = newPalindrome;
        }
    }

You can run it here: http://ideone.com/StCw4u