# 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

hash table rocks

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.