HiveBrain v1.2.0
Get Started
← Back to all entries
patterncsharpMinor

Largest Palindrome efficiency

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
largestpalindromeefficiency

Problem

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

Solution

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

  • Start from the end and work your way back, that way once you've found one palindrome you're done!



  • You only have to check half of the digits for equality.



  • 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
    }
}

Code Snippets

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
    }
}

Context

StackExchange Code Review Q#25193, answer score: 5

Revisions (0)

No revisions yet.