ISourceCode

Make the frequent cases fast and the rare case correct

Algorithm to check if a number can be rearranged to form a Palindrome

This is a slight modification of the Palindrome check question.

Can a number be arranged in such a way to form a palindrome:
Algorithm:
1. Find out the occurrence of each character
2. Only one character with odd occurrence is allowed because in a palindrome maximum number of character with odd occurrence can be 1
3. All other character should occur for even number of times
4. If condition 1, 2 and 3 does not satisfy then palindrome is not possible out of the string.

This approach was used for finding if a string is anagram of another string

#include<iostream>
using namespace std;

bool PossiblePal(char *s)
{
         int array[256]={0}, Odd=0;
  
         //Refer to anagram article similar approach is used
         while(*s!='\0')
         {
           array[(int)*s]+=1;
           s++;
         }
         
         for(int i=0;i<256;i++)
         {
           //On encountering character with odd occurance
           if(array[i]%2!=0 && Odd==0)
             Odd=1;
           //If one more charcter with odd occurances
           else if(array[i]%2!=0 && Odd==1)
             return false;
         }
  
         return true;
}
 
int main()
{
         char str[100];
         cout<<"\nEnter the Number to be checked :\n";
         cin.getline(str, 100);
         if(PossiblePal(str))
           cout<<"Palindrome is possible \n";
         else
           cout<<"Palindrome is NOT possible \n";
  
         return 0;
}

OUTPUT:

laptop:~/code$ ./a.out

Enter the Number to be checked :
1144
Palindrome is possible

laptop:~/code$ ./a.out

Enter the Number to be checked :
11133
Palindrome is possible

laptop:~/code$ ./a.out

Enter the Number to be checked :
123
Palindrome is NOT possible

About these ads

2 responses to “Algorithm to check if a number can be rearranged to form a Palindrome

  1. Arjun Mukherji January 27, 2011 at 1:41 am

    hash table rocks

    • chinmaylokesh January 27, 2011 at 2:17 am

      Yeah true. implementing an actual hash table will be excellent and thanks for the idea. Please post your code if you have implemented already or i will post it in near future.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: