Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.
Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].
Example 1:
Input: left = "4", right = "1000" Output: 4 Explanation: 4, 9, 121, and 484 are superpalindromes. Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.
Example 2:
Input: left = "1", right = "2" Output: 1
Constraints:
1 <= left.length, right.length <= 18left and right consist of only digits.left and right cannot have leading zeros.left and right represent integers in the range [1, 1018 - 1].left is less than or equal to right.Problem summary: Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome. Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
"4" "1000"
"1" "2"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #906: Super Palindromes
class Solution {
private static long[] ps;
static {
ps = new long[2 * (int) 1e5];
for (int i = 1; i <= 1e5; i++) {
String s = Integer.toString(i);
String t1 = new StringBuilder(s).reverse().toString();
String t2 = new StringBuilder(s.substring(0, s.length() - 1)).reverse().toString();
ps[2 * i - 2] = Long.parseLong(s + t1);
ps[2 * i - 1] = Long.parseLong(s + t2);
}
}
public int superpalindromesInRange(String left, String right) {
long l = Long.parseLong(left);
long r = Long.parseLong(right);
int ans = 0;
for (long p : ps) {
long x = p * p;
if (x >= l && x <= r && isPalindrome(x)) {
++ans;
}
}
return ans;
}
private boolean isPalindrome(long x) {
long y = 0;
for (long t = x; t > 0; t /= 10) {
y = y * 10 + t % 10;
}
return x == y;
}
}
// Accepted solution for LeetCode #906: Super Palindromes
var ps [2 * 100000]int64
func init() {
for i := 1; i <= 100000; i++ {
s := strconv.Itoa(i)
t1 := reverseString(s)
t2 := reverseString(s[:len(s)-1])
ps[2*i-2], _ = strconv.ParseInt(s+t1, 10, 64)
ps[2*i-1], _ = strconv.ParseInt(s+t2, 10, 64)
}
}
func reverseString(s string) string {
cs := []rune(s)
for i, j := 0, len(cs)-1; i < j; i, j = i+1, j-1 {
cs[i], cs[j] = cs[j], cs[i]
}
return string(cs)
}
func superpalindromesInRange(left string, right string) (ans int) {
l, _ := strconv.ParseInt(left, 10, 64)
r, _ := strconv.ParseInt(right, 10, 64)
isPalindrome := func(x int64) bool {
var y int64
for t := x; t > 0; t /= 10 {
y = y*10 + int64(t%10)
}
return x == y
}
for _, p := range ps {
x := p * p
if x >= l && x <= r && isPalindrome(x) {
ans++
}
}
return
}
# Accepted solution for LeetCode #906: Super Palindromes
ps = []
for i in range(1, 10**5 + 1):
s = str(i)
t1 = s[::-1]
t2 = s[:-1][::-1]
ps.append(int(s + t1))
ps.append(int(s + t2))
class Solution:
def superpalindromesInRange(self, left: str, right: str) -> int:
def is_palindrome(x: int) -> bool:
y, t = 0, x
while t:
y = y * 10 + t % 10
t //= 10
return x == y
l, r = int(left), int(right)
return sum(l <= x <= r and is_palindrome(x) for x in map(lambda x: x * x, ps))
// Accepted solution for LeetCode #906: Super Palindromes
/**
* [0906] Super Palindromes
*
* Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.
* Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].
*
* Example 1:
*
* Input: left = "4", right = "1000"
* Output: 4
* Explanation: 4, 9, 121, and 484 are superpalindromes.
* Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.
*
* Example 2:
*
* Input: left = "1", right = "2"
* Output: 1
*
*
* Constraints:
*
* 1 <= left.length, right.length <= 18
* left and right consist of only digits.
* left and right cannot have leading zeros.
* left and right represent integers in the range [1, 10^18 - 1].
* left is less than or equal to right.
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/super-palindromes/
// discuss: https://leetcode.com/problems/super-palindromes/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
impl Solution {
// Credit: https://leetcode.com/problems/super-palindromes/solutions/1197431/rust-backtracking-solution/
pub fn superpalindromes_in_range(left: String, right: String) -> i32 {
let mut result = 0;
if let (Ok(l), Ok(r)) = (left.parse::<u64>(), right.parse::<u64>()) {
{
let mut v = Vec::with_capacity(6);
Self::dfs_helper(&mut result, &mut v, &(l..=r), false);
}
{
let mut v = Vec::with_capacity(6);
Self::dfs_helper(&mut result, &mut v, &(l..=r), true);
}
}
result
}
fn dfs_helper(
answer: &mut i32,
v: &mut Vec<u64>,
range: &std::ops::RangeInclusive<u64>,
odd: bool,
) {
if v.len() == 6 {
let digits = if let Some(pos) = v.iter().position(|&d| d != 0) {
&v[pos..]
} else {
&v
};
let mut n = 0;
for &d in digits.iter() {
n = n * 10 + d;
}
for &d in digits.iter().rev().skip(if odd { 1 } else { 0 }) {
n = n * 10 + d;
}
if range.contains(&(n.saturating_mul(n))) {
*answer += 1;
}
} else {
let sum = v.iter().map(|d| d * d).sum::<u64>();
for u in 0..=9 {
if sum * 2 + u * u * if odd { 1 } else { 2 } < 10 {
v.push(u);
Self::dfs_helper(answer, v, range, odd);
v.pop();
}
}
}
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_0906_example_1() {
let left = "4".to_string();
let right = "1000".to_string();
let result = 4;
assert_eq!(Solution::superpalindromes_in_range(left, right), result);
}
#[test]
fn test_0906_example_2() {
let left = "4".to_string();
let right = "1000".to_string();
let result = 4;
assert_eq!(Solution::superpalindromes_in_range(left, right), result);
}
}
// Accepted solution for LeetCode #906: Super Palindromes
const ps = Array(2e5).fill(0);
const init = (() => {
for (let i = 1; i <= 1e5; ++i) {
const s: string = i.toString();
const t1: string = s.split('').reverse().join('');
const t2: string = s.slice(0, -1).split('').reverse().join('');
ps[2 * i - 2] = parseInt(s + t1, 10);
ps[2 * i - 1] = parseInt(s + t2, 10);
}
})();
function superpalindromesInRange(left: string, right: string): number {
const l = BigInt(left);
const r = BigInt(right);
const isPalindrome = (x: bigint): boolean => {
const s: string = x.toString();
return s === s.split('').reverse().join('');
};
let ans = 0;
for (const p of ps) {
const x = BigInt(p) * BigInt(p);
if (x >= l && x <= r && isPalindrome(x)) {
++ans;
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.