906. Super Palindromes
Problem Explanation
In the problem, we are asked to count Super-Palindromes between two given positive integers L and R. A positive integer is called a Super-Palindrome if it is a Palindrome and it is a square of a palindrome as well.
A Palindrome is a string which is similar when reading from start to end and end to start. e.g. "121", "12321", "1"
Solution Approach
If we analyze the problem, it is quite clear that we need to find all the palindrome numbers between sqrt(L) and sqrt(R) then check if the square of that number is also a palindrome.
The time complexity of this program is O(sqrt(n)) and space complexity is O(1).
Let's take an example to understand the approach:
Example 1: Input: L = "4", R = "1000" Output: 4
The numbers between sqrt(L) = sqrt(4) = 2 and sqrt(R) = sqrt(1000) = 31 are 2, 3, 11, 22, 121, 111, 121, 222, 232,......, 313.
Among these 11, 22, 111, 121, 212 are palindromes. Their squares are 121, 484, 12321, 14641, 44944 which are also palindromes. Therefore we conclude that there are 4 superpalindromes in the range.
Python Solution
1 2 3class Solution: 4 def superpalindromesInRange(self, L: str, R: str) -> int: 5 def is_palindrome(n): 6 return str(n) == str(n)[::-1] 7 8 def next_palindrome(n): 9 s = str(n) 10 l = len(s) 11 half = s[:l // 2] 12 ret = int(half + s[(l - 1) // 2] + half[::-1]) 13 if ret < n: 14 return int(str(int(s[:l // 2 + 1]) + (s[:l // 2 + 1][::-1])[l%2:])) 15 return ret 16 17 l, r = int(L), int(R) 18 lb, ub = int(l ** 0.5), int((r + 1) ** 0.5) 19 ans = lb * lb == l 20 if lb * lb != l: 21 lb = next_palindrome(lb) 22 for x in range(lb, ub + 1): 23 if is_palindrome(x ** 2): 24 ans += 1 25 x = next_palindrome(x) 26 27 return ans
Java Solution
1
2
3class Solution {
4 public int superpalindromesInRange(String L, String R) {
5 long l = Long.parseLong(L), r = Long.parseLong(R);
6 int cnt = 0;
7 for (long i = (long)Math.ceil(Math.sqrt(l)); i <= (long)Math.sqrt(r);) {
8 long palindrome = updateToNextPalindrom(i);
9 if (Math.sqrt(palindrome) == Math.floor(Math.sqrt(palindrome)) && isPalindrom(String.valueOf(palindrome))) cnt++;
10 i++;
11 }
12 return cnt;
13 }
14
15 private boolean isPalindrom(String s) {
16 int i = 0, j = s.length();
17 while (i < j) {
18 if (s.charAt(i++) != s.charAt(j--)) return false;
19 }
20 return true;
21 }
22
23 private long updateToNextPalindrom(long n) {
24 char[] s = String.valueOf(n).toCharArray();
25 int len = s.length;
26 for (int i = len / 2; i < len; i++) {
27 s[i] = s[len - i - 1];
28 }
29 long ret = Long.parseLong(new String(s));
30 if (ret < n) {
31 int half = Integer.parseInt(new String(s, 0, len / 2 + 1));
32 half++;
33 char[] halfArr = String.valueOf(half).toCharArray();
34 for (int i = 0; i <= len / 2; i++) {
35 s[i] = halfArr[i];
36 }
37 for (int i = len / 2; i < len; i++) {
38 s[i] = s[len - i - 1];
39 }
40 ret = Long.parseLong(new String(s));
41 }
42 return ret;
43 }
44}
45
Note: Unfortunately, I am not proficient in JavaScript, C++, C#. However, the logic would remain the same; only syntax would differ.# JavaScript Solution
JavaScript solution for this problem goes like this:
We keep generating next higher palindrome numbers, check whether the square of the palindrome is a palindrome and also lies within the given range.
To get next palindrome, we can do that by splitting the number half, reverse it and attach it to the number. Increment the number if it is smaller than the current number.
Here is the JavaScript Solution for the problem:
1
2javascript
3function superpalindromesInRange(left, right) {
4 let L = parseInt(left), R = parseInt(right);
5 let LOW = Math.floor(Math.sqrt(L)), HIGH = Math.ceil(Math.sqrt(R));
6 let cnt = 0;
7
8 for(let i = LOW; i <= HIGH;){
9 let p = createPalindrome(i);
10 if (p > i) i = p;
11 else {
12 if (p*p <= R && isPalindrome(p*p)) cnt++;
13 i = nextNumber(i);
14 }
15 }
16 return cnt;
17};
18
19function createPalindrome(n) {
20 let s = n.toString().split('');
21 let len = s.length;
22 let ret = s.slice(0, Math.floor(len/2)).concat(s[Math.floor((len - 1)/2)]).concat(s.slice(0, Math.floor(len/2)).reverse()).join('');
23 return parseInt(ret);
24}
25
26function nextNumber(n) {
27 let len = n.toString().length;
28 let increment = Math.pow(10, Math.floor(len/2));
29 n = Math.floor(n / increment) * increment + increment;
30 return n;
31};
32
33function isPalindrome(n) {
34 let s = n.toString();
35 let len = s.length;
36 for(let i = 0; i < len / 2; i++) {
37 if(s[i] !== s[len - 1 - i]) {
38 return false;
39 }
40 }
41 return true;
42};
In all solutions, the key idea for counting super-palindromes is to generate palindrome candidates and filter out those that are not super-palindromes. This approach significantly reduces the search space and allows for efficient computation.
Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?
Solution Implementation
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Patterns The Shortest Path Algorithm for Coding Interviews The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we can determine the
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.