Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
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
Output: Palindrome not found
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
- We will store the occurrences of every digit that is occurring in the number.
- 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.
- 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
- 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.
- 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.
- After completing the traversal, we will add that digit which is occurring odd times and make its occurrence zero.
- 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.
- 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)
{
cout<<"Palindrome Not Found";
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.
Intialize a varible Answer = 0. This will store our answer.
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!!)
Answer = 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
^
|
(Take half and subtract half)
Answer = 3
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)
Answer = 32
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)
Answer = 321
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)
Answer = 321
step 3: Add the digit which was occurring odd number of times. Here it is 4.
Answer = 3214
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
^
|
(Add all the remaining occurrences)
Answer = 32141
Frequency array:
occurrences 0 0 1 1 0 0 0 0 0 0
index 0 1 2 3 4 5 6 7 8 9
^
|
(Add all the remaining occurrences)
Answer = 321412
Frequency array:
occurrences 0 0 0 1 0 0 0 0 0 0
index 0 1 2 3 4 5 6 7 8 9
^
|
(Add all the remaining occurrences)
Answer = 3214123
We have obtained the Longest Palindromic Number By Rearranging the digits. With this article at OpenGenus, you should now have a complete about solving this problem with a greedy approach.
Learn more:
- Greedy Algorithms at OpenGenus
