# Largest Palindromic Number by Rearranging Digits

#### Algorithms Greedy Algorithms

Get FREE domain for 1st year and build your brand new site

Given N (very large), we need to find the largest palindromic number by rearranging digits. If it is not possible to print the largest palindromic number from N then, print "Palindrome not found" without double quotes.

Examples:

Input: N = 113223

Output: 321123

Input: N = 333

Output: 333

Inuput: N = 123



# Naive Approach

Find all the palindromic permutations of the digits in N and print out the maximum from it.

Example:

Input: N = 1122

Pallindromic Permutations:
1. 1212
2. 1221
3. 2121
4. 2112
Among these values 2121 is the largest. So, we print 2121 as the largest palindromic number we can get from N(1122).


The Naive Approach will be too slow to calculate the answer when N is very large.

# Efficient Approach

1. We will store the occurrences of every digit that is occurring in the number.
2. Now, we count the number of digits that are occurring odd number of times. If the count is 0 or 1 then we can form a palindrome by rearranging the digits of given number. Otherwise, we cannot make palindrome of given number.
3. If we can form a palindrome by rearranging the digits of given number then apply Greedy approach to obtain the largest palindromic number.

# The Greedy Approach

1. To make a number large we have to put the largest digit at first. Therefore, we start checking the occurrences of every digit from 9 to 0.
2. Now, if the occurrences of the digit is even, then we put half of the occurrence at front and subtract that half from the actual occurrences of current digit and move to the next digit.
3. After completing the traversal, we will add that digit which is occurring odd times and make its occurrence zero.
4. Now, we traverse the digits again but now from 0 to 9 and we will keep adding the remaining occurrences of digits to the number we obtained in step 3.
5. After step 4 we will be having The Largest Palindromic Number.

Important Points we need to remember while coding the solution-:

• The number can be very large so we need to store it in a string.
• To store the occurrences of the digits we will use a count array of size 10.
• We should include a function which will check if the given number can form a palindrome number or not.

C++ Code

#include<bits/stdc++.h>
using namespace std;

string theLargestPalindromicNumber;//This will contain the answer, right now it is empty.

bool possiblePalindrome(int count[], int length)
{
int numberOfOdds = 0;

for(int i=0;i<length;i++)
{
if(count[i] & 1)// it will give 1 if the count is odd otherwise 0 will be the output.
{
numberOfOdds++;
}
}

if(numberOfOdds>1)
return false;
else
return true;
}

void largestPalindromicNumber(string number)
{
int length = number.size();
int count[10]={0};//to store count of digits.

//Step 1

for(int i=0;i<length;i++)
{
count[number[i] - '0']++;
}

// check if we can form a palindrome or not.

if(possiblePalindrome(count, length) == false)
{
return ;
}//step 1 ends
else
{
// Now we can make palindromic numbers from the given input.

int indexOfOddTimesOccuringDiigit = -1;// -1 indicates, no digit is occurring odd number of times.

//Step 2 starts

for(int i=9; i>=0; i--)
{
if(count[i]&1)
{
indexOfOddTimesOccuringDiigit = i;
}
else
{
for(int j = 0; j < count[i]/2; j++)
{
theLargestPalindromicNumber+= char(i + 48);
}
count[i]/=2;
}
}
//step 2 ends

//step 3 starts

if(indexOfOddTimesOccuringDiigit!=-1)
{

for(int i = 0; i<count[indexOfOddTimesOccuringDiigit]; i++)
{
theLargestPalindromicNumber+= char(indexOfOddTimesOccuringDiigit + 48);
}

count[indexOfOddTimesOccuringDiigit] = 0;

}
//step 3 ends

//step 4 starts

for(int i=0; i<=9; i++)
{
for(int j=0; j<count[i]; j++)
{
theLargestPalindromicNumber+= char(i + 48);
}
}
//step 4 ends
}
return ;

}
int main()
{
string number;
cin>>number;
largestPalindromicNumber(number);

//step 5 starts
cout<<theLargestPalindromicNumber;
//step 5 ends
return 0;

}


In the worst case, the time complexity will be O(10 * (length of string/2)), in case the number consists of a same digit at every position.

Time Complexity: O(N)

Example:

N = 1122334


step 1: Count the digits having odd occurences.

Frequency array:
occurrences  0 2 2 2 1 0 0 0 0 0
index        0 1 2 3 4 5 6 7 8 9


We have 1 digit whose occurrence is odd. So this is a valid number, we can form a palindrome.

step 2: Start travesing from 9, till 0.

Frequency array:
occurrences  0 2 2 2 1 0 0 0 0 0
index        0 1 2 3 4 5 6 7 8 9
^
|
(Odd Occurrence we will add it later!!)


Frequency array:
occurrences  0 2 2 2 1 0 0 0 0 0
index        0 1 2 3 4 5 6 7 8 9
^
|
(Take half and subtract half)


Frequency array:
occurrences  0 2 2 1 1 0 0 0 0 0
index        0 1 2 3 4 5 6 7 8 9
^
|
(Take half and subtract half)


Frequency array:
occurrences  0 2 1 1 1 0 0 0 0 0
index        0 1 2 3 4 5 6 7 8 9
^
|
(Take half and subtract half)


Frequency array:
occurrences  0 1 1 1 1 0 0 0 0 0
index        0 1 2 3 4 5 6 7 8 9
^
|
(It is zero)


step 3: Add the digit which was occurring odd number of times. Here it is 4.

step 4: Traverse from 0, till 9.

Frequency array:
occurrences  0 1 1 1 0 0 0 0 0 0
index        0 1 2 3 4 5 6 7 8 9
^
|


Frequency array:
occurrences  0 0 1 1 0 0 0 0 0 0
index        0 1 2 3 4 5 6 7 8 9
^
|


Frequency array:
occurrences  0 0 0 1 0 0 0 0 0 0
index        0 1 2 3 4 5 6 7 8 9
^
|