Given two positive integers L and R (represented as strings) where 
. 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 
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 105 and create the associated palindrome R, and check whether R2 is a palindrome.
Also, we will handle the odd and even palindromes separately, and break whenever out palindrome goes beyond R. Now since 
, and 
and 
(on Concatenation), where i‘ is reverse of i (in both ways), so our LIMIT will not be greater than 
.
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 palindromebool 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 palindromesint 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 Codeint 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 approachimport java.lang.*;class GFG{// check if a number is a palindromepublic 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 palindromespublic 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 programpublic 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 palindromedef 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 palindromesdef 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 programL = "4"R = "1000"# function call to get required answerprint(SuperPalindromes(L, R))# This code is written by# Sanjit_Prasad |
C#
// C# implementation of the // above approachusing System;class GFG{// check if a number is a palindromestatic 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 stringstatic string Reverse( string s ){ char[] charArray = s.ToCharArray(); Array.Reverse( charArray ); return new string( charArray );}// Function to return required // count of palindromesstatic 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 Codepublic 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 palindromefunction 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 palindromesfunction 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 answerecho SuperPalindromes($L, $R);// This code is contributed // by Harshit Saini ?> |
Javascript
<script>// JavaScript implementation of the above approach// check if a number is a palindromefunction 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 palindromesfunction 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 programlet L = "4"let R = "1000"// function call to get required answerdocument.write(SuperPalindromes(L, R))// This code is written by// shinjanpatra</script> |
Output
4
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)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
