Count all palindrome which is square of a palindrome

0 0 7 minutes read

Given two positive integers L and R (represented as strings) where $1\leq L \leq R\leq10^{18}$ . The task is to find the total number of super-palindromes in the inclusive range [L, R]. A palindrome is called super-palindrome if it is a palindrome and also square of a palindrome.

Examples:

Input: L = "4", R = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are super-palindromes.

Input : L = "100000", R = "10000000000"
Output : 11

Approach: Lets say $P = R^{2}$ is a super-palindrome. Now since R is a palindrome, the first half of the digits of R can be used to determine R up-to two possibilities. Let i be the first half of the digits in R. For eg. if i = 123, then R = 12321 or R = 123321. Thus we can iterate through these all these digits. Also each possibility can have either odd or even number of digits in R. Thus we iterate through each i upto 10⁵ and create the associated palindrome R, and check whether R² is a palindrome.

Also, we will handle the odd and even palindromes separately, and break whenever out palindrome goes beyond R. Now since $P \leq 10^{18}$ , and $R \leq (10^{18})^{\frac{1}{2}} \equiv 10^{9}$ and $R = i||i^{'}$ (on Concatenation), where i^‘ is reverse of i (in both ways), so our LIMIT will not be greater than $i\leq10^{5}$ .

Below is the implementation of the above approach:

C++

// C++ implementation of the 
// above approach
#include <bits/stdc++.h> 
using namespace std;
 
// check if a number is a palindrome
bool ispalindrome(int x)
{
    int ans = 0;
    int temp = x;
    while (temp > 0)
    {
        ans = 10 * ans + temp % 10;
        temp = temp / 10;
    }
    return ans == x;
}
 
// Function to return required count 
// of palindromes
int SuperPalindromes(int L, int R)
{
    // Range [L, R]
 
    // Upper limit
    int LIMIT = 100000;
 
    int ans = 0;
 
    // count odd length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
        string s = to_string(i); // if s = '1234'
 
        string rs = s.substr(0, s.size() - 1);
        reverse(rs.begin(), rs.end());
 
        // then, t = '1234321'
        string p = s + rs; 
        int p_sq     = pow(stoi(p), 2);
        if (p_sq > R)
            break;
        if (p_sq >= L and ispalindrome(p_sq))
            ans = ans + 1;
    }
 
    // count even length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
        string s = to_string(i); // if s = '1234'
 
        string rs = s;
        reverse(rs.begin(), rs.end());
        string p = s + rs; // then, t = '12344321'
        int p_sq = pow(stoi(p), 2);
        if (p_sq > R)
            break;
        if (p_sq >= L and ispalindrome(p_sq))
            ans = ans + 1;
    }
 
    // Return count of super-palindromes
    return ans;
}
 
// Driver Code
int main()
{
    string L = "4";
    string R = "1000";
     
    // function call to get required answer
    printf("%d\n", SuperPalindromes(stoi(L), 
                                  stoi(R)));
    return 0;
} 
 
// This code is contributed 
// by Harshit Saini

Java

// Java implementation of the
// above approach
import java.lang.*;
 
class GFG
{
 
// check if a number is a palindrome
public static boolean ispalindrome(int x)
{
    int ans = 0;
    int temp = x;
    while (temp > 0)
    {
        ans = 10 * ans + temp % 10;
        temp = temp / 10;
    }
    return ans == x;
}
 
// Function to return required 
// count of palindromes
public static int SuperPalindromes(int L, 
                                   int R)
{
    // Range [L, R]
 
    // Upper limit
    int LIMIT = 100000;
 
    int ans = 0;
 
    // count odd length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
 
        // if s = '1234'
        String s = Integer.toString(i);
 
        StringBuilder rs = new StringBuilder();
        rs.append(s.substring(0,
                     Math.max(1, s.length() - 1)));
        String srs = rs.reverse().toString();
 
        // then, t = '1234321'
        String p = s + srs;
        int p_sq = (int)(Math.pow(
                         Integer.parseInt(p), 2));
        if (p_sq > R)
        {
            break;
        }
        if (p_sq >= L && ispalindrome(p_sq))
        {
            ans = ans + 1;
        }
    }
 
    // count even length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
 
        // if s = '1234'
        String s = Integer.toString(i); 
 
        StringBuilder rs = new StringBuilder();
        rs.append(s);
        rs = rs.reverse();
 
        String p = s + rs; // then, t = '12344321'
        int p_sq = (int)(Math.pow(
                         Integer.parseInt(p), 2));
        if (p_sq > R)
        {
            break;
        }
        if (p_sq >= L && ispalindrome(p_sq))
        {
            ans = ans + 1;
        }
    }
 
    // Return count of super-palindromes
    return ans;
}
 
// Driver program
public static void main(String [] args)
{
    String L = "4";
    String R = "1000";
 
    // function call to get required answer
    System.out.println(SuperPalindromes(
       Integer.parseInt(L), Integer.parseInt(R)));
}
}
 
// This code is contributed 
// by Harshit Saini 

Python3

# Python implementation of the above approach
 
# check if a number is a palindrome
def ispalindrome(x):
    ans, temp = 0, x
    while temp > 0:
        ans = 10 * ans + temp % 10
        temp = temp // 10
    return ans == x
 
# Function to return required count of palindromes
def SuperPalindromes(L, R):
    # Range [L, R]
    L, R = int(L), int(R)
 
    # Upper limit
    LIMIT = 100000
 
    ans = 0
 
    # count odd length palindromes
    for i in range(LIMIT):
        s = str(i)  # if s = '1234'
        p = s + s[-2::-1]  # then, t = '1234321'
        p_sq = int(p) ** 2
        if p_sq > R:
            break
        if p_sq >= L and ispalindrome(p_sq):
            ans = ans + 1
 
    # count even length palindromes
    for i in range(LIMIT):
        s = str(i)  # if s = '1234'
        p = s + s[::-1]  # then, t = '12344321'
        p_sq = int(p) ** 2
        if p_sq > R:
            break
        if p_sq >= L and ispalindrome(p_sq):
            ans = ans + 1
 
    # Return count of super-palindromes
    return ans
 
# Driver program
L = "4"
R = "1000"
 
# function call to get required answer
print(SuperPalindromes(L, R))
 
# This code is written by
# Sanjit_Prasad

C#

// C# implementation of the 
// above approach
using System;
 
class GFG
{
 
// check if a number is a palindrome
static bool ispalindrome(int x)
{
    int ans = 0;
    int temp = x;
    while (temp > 0)
    {
        ans = 10 * ans + temp % 10;
        temp = temp / 10;
    }
    return ans == x;
}
 
// utility function used for 
// reversing a string
static string Reverse( string s )
{
    char[] charArray = s.ToCharArray();
    Array.Reverse( charArray );
    return new string( charArray );
}
 
// Function to return required 
// count of palindromes
static int SuperPalindromes(int L, int R)
{
    // Range [L, R]
 
    // Upper limit
    int LIMIT = 100000;
 
    int ans = 0;
 
    // count odd length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
 
        // if s = '1234'
        string s = i.ToString();
 
        string rs = s.Substring(0,
                       Math.Max(1, s.Length - 1));
        rs = Reverse(rs);
 
        // then, t = '1234321'
        string p = s + rs;
        int p_sq = (int)(Math.Pow(
                            Int32.Parse(p), 2));
        if (p_sq > R)
        {
            break;
        }
        if (p_sq >= L && ispalindrome(p_sq))
        {
            ans = ans + 1;
        }
    }
 
    // count even length palindromes
    for (int i = 0 ;i < LIMIT; i++)
    {
 
        // if s = '1234'
        string s = i.ToString();
 
        string rs = Reverse(s);
 
        string p = s + rs; // then, t = '12344321'
        int p_sq = (int)(Math.Pow(
                            Int32.Parse(p), 2));
        if (p_sq > R)
        {
            break;
        }
        if (p_sq >= L && ispalindrome(p_sq))
        {
            ans = ans + 1;
        }
    }
 
    // Return count of super-palindromes
    return ans;
}
 
// Driver Code
public static void Main()
{
    string L = "4";
    String R = "1000";
 
    // function call to get required answer
    Console.WriteLine(SuperPalindromes(
            Int32.Parse(L), Int32.Parse(R)));
}
}
 
// This code is contributed 
// by Harshit Saini 

PHP

<?php 
// PHP implementation of the 
// above approach
 
// check if a number is a palindrome
function ispalindrome($x)
{
    $ans = 0;
    $temp = $x;
 
    while($temp > 0)
    {     
        $ans = (10 * $ans) +
               ($temp % 10);
        $temp = (int)($temp / 10);
    }
 
    return $ans == $x;
}
 
// Function to return required
// count of palindromes
function SuperPalindromes($L, $R)
{
    // Range [L, R]
    $L = (int)$L;
    $R = (int)$R;
 
    // Upper limit
    $LIMIT = 100000;
 
    $ans = 0;
 
    // count odd length palindromes
    for($i = 0 ;$i < $LIMIT; $i++)
    {
 
        $s = (string)$i; // if s = '1234'
        $rs = substr($s, 0, strlen($s) - 1);
        $p = $s.strrev($rs); // then, t = '1234321'
        $p_sq = (int)$p ** 2;
        if ($p_sq > $R)
        {
            break;
        }
        if ($p_sq >= $L and ispalindrome($p_sq))
        {
            $ans = $ans + 1;
        }
    } 
 
    // count even length palindromes
    for($i = 0 ;$i < $LIMIT; $i++)
    {
        $s = (string)$i; // if s = '1234'
        $p = $s.strrev($s); // then, t = '12344321'
         
        $p_sq = (int)$p ** 2;
 
        if ($p_sq > $R)
        {
            break;
        }
        if ($p_sq >= $L and ispalindrome($p_sq))
        {
            $ans = $ans + 1;
        }
    }
 
    // Return count of super-palindromes
    return $ans;
}
 
 
// Driver Code
$L = "4";
$R = "1000";
 
// function call to get required answer
echo SuperPalindromes($L, $R);
 
// This code is contributed 
// by Harshit Saini 
?>

Javascript

<script>
 
// JavaScript implementation of the above approach
 
// check if a number is a palindrome
function ispalindrome(x){
    let ans = 0,temp = x
    while(temp > 0){
        ans = 10 * ans + temp % 10
        temp = Math.floor(temp / 10)
    }
    return ans == x
}
 
// Function to return required count of palindromes
function SuperPalindromes(L, R)
{
 
    // Range [L, R]
    L = parseInt(L),R = parseInt(R)
 
    // Upper limit
    let LIMIT = 100000
 
    let ans = 0
 
    // count odd length palindromes
    for(let i = 0; i < LIMIT; i++)
    {
        let s = i.toString() // if s = '1234'
        let rs = s.substring(0,s.length-1)
        rs = rs.split('').reverse().join('')
        let p = s + rs // then, t = '1234321'
        let p_sq = Math.pow(parseInt(p),2)
        if(p_sq > R)
            break
        if(p_sq >= L && ispalindrome(p_sq))
            ans = ans + 1
    }
 
    // count even length palindromes
    for(let i = 0; i < LIMIT; i++)
    {
        let s = i.toString() // if s = '1234'
        let rs = s
        rs = rs.split('').reverse().join('')
        let p = s + rs// then, t = '12344321'
        let p_sq = Math.pow(parseInt(p),2)
        if(p_sq > R)
            break
        if(p_sq >= L && ispalindrome(p_sq))
            ans = ans + 1
    }
 
    // Return count of super-palindromes
    return ans
}
 
// Driver program
let L = "4"
let R = "1000"
 
// function call to get required answer
document.write(SuperPalindromes(L, R))
 
// This code is written by
// shinjanpatra
 
</script>

Output

Complexity Analysis:

Time Complexity: O(N*log(N)) where N is upper limit and the log(N) term comes from checking if a candidate is palindrome.
Auxiliary Space: O(LIMIT)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!