patterncsharpMinor
Largest Palindrome efficiency
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:
Something like this:
- 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.