Find Nth even length palindromic number formed using digits X and Y

0 0 6 minutes read

Given an integer N, the task is to find the N^th even palindromic number of even length and only comprising of the digits X and Y where X, Y > 0.
Examples:

Input: N = 9, X = 4, Y = 5
Output: 454454
Explanation:
Even length palindromic numbers using 4 & 5 are
44, 55, 4444, 4554, 5445, 5555, 444444, 445544, 454454, …
9th term of the above series = 454454
Input: N = 6, X = 1, Y = 2
Output: 2222
Explanation:
Even length palindromic numbers using 1 & 2 are
11, 22, 1111, 1221, 2112, 2222, 111111, 112211, 121121, …
6th term of the above series = 2222

Approach:

Even length palindromic numbers using X & Y are

XX, YY, XXXX, XYYX, YXXY, YYYY, XXXXXX, XXYYXX, ...

The above sequence can be observed as:

XX,       -> Length (L) = 2
YY,       -> Length (L) = 2

XXXX,     -> Length (L) = 4
XYYX,     -> Length (L) = 4
YXXY,     -> Length (L) = 4
YYYY,     -> Length (L) = 4

XXXXXX,   -> Length (L) = 6
XXYYXX,   -> Length (L) = 6
XYXXYX,   -> Length (L) = 6
XYYYYX,   -> Length (L) = 6
YXXXXY,   -> Length (L) = 6
YXYYXY,   -> Length (L) = 6
YYXXYY,   -> Length (L) = 6
YYYYYY,   -> Length (L) = 6

XXXXXXXX, -> Length (L) = 8
...

If we divide any term into 2 halves, the second half is just the reverse of the first half
Example:

Taking the term XXYYXX

Dividing this into 2 halves
XXYYXX = XXY | YXX

So YXX is just the reverse of XXY

Taking the left half only of the terms and putting X = 0 and Y = 1 to get the Binary String, the numbers of length L can be seen forming a integer sequence from 0 to (2^L/2 – 1), taken as Rank (R). Therefore 0 &leq; R &leq; 2^L/2 – 1
Therefore the sequence can be observed as follows:

L -> Left Half -> Binary String -> Rank (in Decimal) 

2 -> X    -> 0             -> 0
2 -> Y    -> 1             -> 1

4 -> XX   -> 00            -> 0
4 -> XY   -> 01            -> 1
4 -> YX   -> 10            -> 2
4 -> YY   -> 11            -> 3

6 -> XXX  -> 000           -> 0
6 -> XXY  -> 001           -> 1
6 -> XYX  -> 010           -> 2
6 -> XYY  -> 011           -> 3
6 -> YXX  -> 100           -> 4
6 -> YXY  -> 101           -> 5
6 -> YYX  -> 110           -> 6
6 -> YYY  -> 111           -> 7

8 -> XXXX -> 0000          -> 0
...

Therefore, For the required term N:

The length (L) of the required Nth term:

$L=2(\left\lceil log_{2}(N + 2)\right\rceil-1)$
Rank (R) of the required Nth term:

$R = N - 2^{(\frac{L}{2})} + 1$
First Half of the required Nth term = Binary representation of R in L/2 bits by replacing 0 as X and 1 as Y
Second Half of the required Nth term = Reverse of the First Half

Below is the implementation of the above approach:

C++

// C++ program to find nth even 
// palindromic number of only even 
// length composing of 4's and 5's. 
  
#include <bits/stdc++.h> 
using namespace std; 
  
// Utility function to compute 
// n'th palindrome number 
string solve(int n, char x, char y) 
{ 
    // Calculate the length from above 
    // formula as discussed above 
    int length = ceil(log2(n + 2)) - 1; 
  
    // Calculate rank for length L 
    int rank = n - (1 << length) + 1; 
  
    string left = "", right = ""; 
  
    for (int i = length - 1; i >= 0; i--) { 
  
        // Mask to check if i't bit 
        // is set or not 
        int mask = 1 << i; 
  
        // If bit is set append '5' else append '4' 
        bool bit = mask & rank; 
  
        if (bit) { 
            left += y; 
            right += y; 
        } 
        else { 
            left += x; 
            right += x; 
        } 
    } 
  
    reverse(right.begin(), right.end()); 
  
    return left + right; 
} 
  
// Driver Code 
int main() 
{ 
    int n = 23; 
    char x = '4', y = '5'; 
    string ans = solve(n, x, y); 
    cout << ans << '\n'; 
  
    return 0; 
} 

Java

// Java program to find nth even  
// palindromic number of only even  
// length composing of 4's and 5's.  
import java.util.*; 
  
class GFG 
{ 
      
    // Utility function to compute  
    // n'th palindrome number  
    static String solve(int n, char x, char y)  
    {  
        // Calculate the length from above  
        // formula as discussed above  
        int length = (int)Math.ceil(Math.log(n + 2) /  
                                    Math.log(2)) - 1;  
      
        // Calculate rank for length L  
        int rank = n - (1 << length) + 1;  
      
        String left = "", right = "";  
      
        for (int i = length -1 ; i >= 0; i--) 
        {  
      
            // Mask to check if i't bit  
            // is set or not  
            int mask = (1 << i);  
      
            // If bit is set append '5' else append '4'  
            int bit = mask & rank;  
              
            if (bit > 0) 
            {  
                left += y;  
                right += y;  
            }  
            else 
            {  
                left += x;  
                right += x;  
            }  
        }  
          
        StringBuilder sb = new StringBuilder(right);  
        sb.reverse();  
          
        right = sb.toString();  
          
        String res = left + right; 
        return res;  
    }  
      
    // Driver Code  
    public static void main (String[] args) 
    {  
        int n = 23;  
        char x = '4', y = '5';  
        String ans = solve(n, x, y);  
        System.out.println(ans);  
    }  
} 
  
// This code is contributed by AnkitRai01 

Python3

# Python3 program to find nth even  
# palindromic number of only even  
# length composing of 4's and 5's.  
from math import ceil, log2 
  
# Utility function to compute  
# n'th palindrome number  
def solve(n, x, y) :  
  
    # Calculate the length from above  
    # formula as discussed above  
    length = ceil(log2(n + 2)) - 1;  
  
    # Calculate rank for length L  
    rank = n - (1 << length) + 1;  
  
    left = ""; right = "";  
  
    for i in range(length - 1 , -1, -1): 
  
        # Mask to check if i't bit  
        # is set or not  
        mask = (1 << i);  
  
        # If bit is set append '5'  
        # else append '4'  
        bit = (mask & rank);  
  
        if (bit) : 
            left += y;  
            right += y;  
              
        else : 
            left += x;  
            right += x;  
  
    right = right[::-1]; 
      
    res = left + right; 
    return res; 
  
# Driver Code  
if __name__ == "__main__" :  
  
    n = 23;  
    x = '4'; 
    y = '5';  
    ans = solve(n, x, y);  
    print(ans);  
      
# This code is contributed by kanugargng 

C#

// C# program to find nth even  
// palindromic number of only even  
// length composing of 4's and 5's.  
using System; 
  
class GFG 
{ 
      
    // Utility function to compute  
    // n'th palindrome number  
    static String solve(int n, char x, char y)  
    {  
        // Calculate the length from above  
        // formula as discussed above  
        int length = (int)Math.Ceiling(Math.Log(n + 2) /  
                                       Math.Log(2)) - 1;  
      
        // Calculate rank for length L  
        int rank = n - (1 << length) + 1;  
      
        String left = "", right = "";  
      
        for (int i = length -1; i >= 0; i--) 
        {  
      
            // Mask to check if i't bit  
            // is set or not  
            int mask = (1 << i);  
      
            // If bit is set append '5' 
            // else append '4'  
            int bit = mask & rank;  
              
            if (bit > 0) 
            {  
                left += y;  
                right += y;  
            }  
            else
            {  
                left += x;  
                right += x;  
            }  
        }  
          
        right = reverse(right); 
        String res = left + right; 
        return res;  
    }  
      
    static String reverse(String input)  
    { 
        char[] a = input.ToCharArray(); 
        int l, r = 0; 
        r = a.Length - 1; 
  
        for (l = 0; l < r; l++, r--)  
        { 
            // Swap values of l and r  
            char temp = a[l]; 
            a[l] = a[r]; 
            a[r] = temp; 
        } 
        return String.Join("", a); 
    }  
      
    // Driver Code  
    public static void Main (String[] args) 
    {  
        int n = 23;  
        char x = '4', y = '5';  
        String ans = solve(n, x, y);  
        Console.WriteLine(ans);  
    }  
} 
  
// This code is contributed by Rajput-Ji 

Javascript

<script> 
  
// Javascript program to find nth even 
// palindromic number of only even 
// length composing of 4's and 5's. 
  
// Utility function to compute 
// n'th palindrome number 
function solve(n, x, y) 
{ 
    // Calculate the length from above 
    // formula as discussed above 
    var length = Math.ceil(Math.log2(n + 2)) - 1; 
  
    // Calculate rank for length L 
    var rank = n - (1 << length) + 1; 
  
    var left = "", right = ""; 
  
    for (var i = length - 1; i >= 0; i--) { 
  
        // Mask to check if i't bit 
        // is set or not 
        var mask = 1 << i; 
  
        // If bit is set append '5' else append '4' 
        var bit = mask & rank; 
  
        if (bit) { 
            left += y; 
            right += y; 
        } 
        else { 
            left += x; 
            right += x; 
        } 
    } 
  
    right = right.split('').reverse().join(''); 
  
    return left + right; 
} 
  
// Driver Code 
var n = 23; 
var x = '4', y = '5'; 
var ans = solve(n, x, y); 
document.write( ans + "<br>"); 
  
</script>

Output

54444445

Time Complexity: $O(n)$ where n is the length of string

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!