Count all palindrome which is square of a palindrome in Java
Given L and R be two positive integers, denoted by strings, such that 1 <= L <= R 1018. The task is to determine how many super-palindromes there are in the inclusive range [L, R]. If a palindrome is both the square of a palindrome and a palindrome, it is called a super-palindrome.
Example 1:
Input:
String L = 4 String R = 1000
Output:
The total number of square palindromes is 4
Explanation:
As the range starts from 4, now the squares present between the range are 4, 9, 16, 25, 49, 64, 81, 100, 121, 144...., 484. In this sequence, the numbers 121, 484, …. which are squares and palindromes. Hence, the total number of square palindromes is 4.
Example 2:
Input:
String L = 100000 String R = 10000000000
Output:
The total number of square palindromes is 11
Explanation:
As the range starts from 100000, now the total number of squares palindromes present between the range is 11.
Example 3:
Input:
String L = 1 String R = 25
Output:
The total number of square palindromes is 0
Explanation:
As the range starts from 4, the squares present between the range are 4, 9, 16, and 25. These numbers are square, but they are not palindromic.
Approach: Naïve Approach
Algorithm:
Step 1: Consider the case when P = R^{2} is a super-palindrome.
Step 2: R can now be determined in up to two ways using the first half of its digits because it is a palindrome.
Step 2.1: Let i represent the initial half of the R digits. R = 12321 or R = 123321, for example, if i = 123.
Step 2.2: We can therefore iterate over each of these digits.
Step 3: Additionally, the number of digits in R for each alternative can be odd or even.
Step 4: In order to determine whether R2 is a palindrome, we iterate through each i up to 105, generate the corresponding palindrome R, and then check.
We will also interpret even and odd palindromes in various ways, breaking anytime our palindrome exceeds R. Assuming that P<= 1018, and R <= (1018)1/2, which are equivalent to 109 and R = i||i` (on concatenation) respectively, where it is the opposite of i (both ways), our LIMIT will not exceed i <= 105.
Implementation:
FileName: SquarePalindromes.java
import java.lang.*; import java.io.*; public class SquarePalindromes { //Check whether the number //Is a palindrome or not public static boolean palindrome(int n) { int result = 0; int temp = n; while (temp > 0) { result = 10 * result + temp % 10; temp = temp / 10; } return result == n; } // Required function to return //The number of palindromes public static int SuperPalindromes(int L, int R) { // Range [L, R] // Upper limit int LIMIT = 100000; int result = 0; // count the number of odd length palindromes for (int i = 0 ;i < LIMIT; i++) { // if str = '1234' String str = Integer.toString(i); StringBuilder strbuild = new StringBuilder(); strbuild.append(str.substring(0, Math.max(1, str.length() - 1))); String srs = strbuild.reverse().toString(); // then, t = '1234321' String p = str + srs; int palin_seq = (int)(Math.pow( Integer.parseInt(p), 2)); if (palin_seq > R) { break; } if (palin_seq >= L && palindrome(palin_seq)) { result = result + 1; } } // count the number of even length palindromes for (int i = 0 ;i < LIMIT; i++) { // if s = '1234' String str = Integer.toString(i); StringBuilder strbuild = new StringBuilder(); strbuild.append(str); strbuild = strbuild.reverse(); String p = str + strbuild; // then, t = '12344321' int palin_seq = (int)(Math.pow( Integer.parseInt(p), 2)); if (palin_seq > R) { break; } if (palin_seq >= L && palindrome(palin_seq)) { result = result + 1; } } // Return the total number of count of super-palindromes return result; } public static void main(String [] args) { String L = "4"; String R = "1000"; System.out.println("The total number of square palindromes is : " + SuperPalindromes( Integer.parseInt(L), Integer.parseInt(R))); } }
Output:
The total number of square palindromes is : 4
Complexity Analysis:
The Time Complexity is O(N*log(N)), where the log(N) term derives from determining whether a candidate is a palindrome, N is the upper limit, and the Space complexity is O(LIMIT).