-
Notifications
You must be signed in to change notification settings - Fork 45
/
_906.java
70 lines (57 loc) · 1.68 KB
/
_906.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import java.util.Set;
import java.util.TreeSet;
/**
* LeetCode 906 - Super Palindromes
*
* Just generate all the candidates under 10^18.
*/
public class _906 {
static Set<Long> superPalindromes = new TreeSet<>();
static long reverse(long n) {
long reverse = 0;
while (n > 0) {
reverse = reverse * 10 + n % 10;
n /= 10;
}
return reverse;
}
static boolean isPalindrome(long n) {
return n == reverse(n);
}
static long pow(long n) {
long pow = 1;
while (n > 0) {
pow *= 10;
n /= 10;
}
return pow;
}
static {
// Length = 1
for (int i = 1; i <= 9; i++) {
if (isPalindrome(i * i)) {
superPalindromes.add(1L * i * i);
}
}
for (int i = 1; i < 100000; i++) {
long first = i, last = reverse(first), pow = pow(first);
// Even length
long palin = first * pow + last;
if (palin <= Integer.MAX_VALUE && isPalindrome(palin * palin)) {
superPalindromes.add(palin * palin);
}
// Odd length
for (int j = 0; j < 10; j++) {
palin = (first * 10 + j) * pow + last;
if (palin <= Integer.MAX_VALUE && isPalindrome(palin * palin)) {
superPalindromes.add(palin * palin);
}
}
}
}
public int superpalindromesInRange(String L, String R) {
long l = Long.parseLong(L);
long r = Long.parseLong(R);
return (int) superPalindromes.stream().filter(palin -> palin >= l && palin <= r).count();
}
}