N’th palindrome of K digits
N’th palindrome of K digits
Given two integers n and k, Find the lexicographical nth palindrome of k digits.
Input : n = 5, k = 4
Output : 1441
Explanation:
4 digit lexicographical palindromes are:
1001, 1111, 1221, 1331, 1441
5th palindrome = 1441
An efficient method is to look for a pattern. According to the property of palindrome first half digits is same as the rest half digits in reverse order. Therefore we only need to look for first half digits as rest of them can easily be generated. Let’s take k = 8, smallest palindrome always starts from 1 as leading digit and goes like that for first 4 digit of number.
First half values for k = 8 1st: 1000 2nd: 1001 3rd: 1002 ... ... 100th: 1099 So we can easily write the above sequence for nth palindrome as: (n-1) + 1000 For k digit number, we can generalize above formula as: If k is odd => num = (n-1) + 10k/2 else => num = (n-1) + 10k/2 - 1 Now rest half digits can be expanded by just printing the value of num in reverse order. But before this if k is odd then we have to truncate the last digit of a value num
void
nthPalindrome(
int
n,
int
k)
{
// Determine the first half digits
int
temp = (k & 1) ? (k / 2) : (k/2 - 1);
int
palindrome = (
int
)
pow
(10, temp);
palindrome += n - 1;
// Print the first half digits of palindrome
printf
(
"%d"
, palindrome);
// If k is odd, truncate the last digit
if
(k & 1)
palindrome /= 10;
// print the last half digits of palindrome
while
(palindrome)
{
printf
(
"%d"
, palindrome % 10);
palindrome /= 10;
}
printf
(
"\n"
);
}
A brute force is to run a loop from smallest kth digit number and check for every number whether it is palindrome or not. If it is palindrome number then decrements the value of k. Therefore the loop runs until k become exhausted.
Time complexity: O(10k)
// Utility function to reverse the number n
int
reverseNum(
int
n)
{
int
rem, rev=0;
while
(n)
{
rem = n % 10;
rev = rev * 10 + rem;
n /= 10;
}
return
rev;
}
// Boolean Function to check for palindromic
// number
bool
isPalindrom(
int
num)
{
return
num == reverseNum(num);
}
// Function for finding nth palindrome of k digits
int
nthPalindrome(
int
n,
int
k)
{
// Get the smallest k digit number
int
num = (
int
)
pow
(10, k-1);
while
(
true
)
{
// check the number is palindrom or not
if
(isPalindrom(num))
--n;
// if n'th palindrome found break the loop
if
(!n)
break
;
// Increment number for checking next palindrome
++num;
}
return
num;
}