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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Which one best describes the time complexity of the following code?
1int factorial(int n) {
2 if (n < 0) {
3 return -1;
4 } else if (n == 0) {
5 return 1;
6 } else {
7 return n * factorial(n - 1);
8 }
9}
Solution Implementation
How does quick sort divide the problem into subproblems?
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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 Teaching 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.