Count Palindromic Numbers in a Range
Solve this ProblemEasy10 min
Topics
BasicsFunctionsMath
Companies
TCSInfosysWipro
Given a range
low to high (inclusive), return how many numbers in it are palindromes — numbers that read the same forwards and backwards, like 7, 44 or 12321.
Checking one number is the job of an isPalindrome(n) helper; counting across a range is the job of the main function. Keeping those two jobs apart is the core idea of separation of concernsSeparation of ConcernsGiving each function one clear responsibility, so it can be understood, tested and changed on its own.: the two solutions swap in completely different helpers, and the counting loop does not change by a single character.
Test Case 1:
Input:low = 1, high = 20
Output:10
Explanation:1 to 9 are all palindromes, and so is 11 — ten in total.
Test Case 2:
Input:low = 100, high = 130
Output:3
Explanation:101, 111 and 121 read the same forwards and backwards.
Constraints
- ◆
1 ≤ low ≤ high ≤ 100000
Try the Dry Run
Approach & Solutions
String Comparison HelperGood
Write isPalindrome(n) that turns n into text and checks whether the text equals its own reverse (C compares characters from both ends). Then loop over every number from low to high and count the ones for which the helper returns true.
Time
O((high − low) · d)Space
O(d)Java
class Solution {
boolean isPalindrome(int n) {
String text = String.valueOf(n);
return text.equals(new StringBuilder(text).reverse().toString());
}
public int countPalindromes(int low, int high) {
int count = 0;
for (int n = low; n <= high; n++) {
if (isPalindrome(n)) {
count++;
}
}
return count;
}
}Arithmetic isPalindrome HelperOptimal
Make the helper avoid strings: rebuild the number in reverse with % 10 and / 10, then compare it with the original. A number is a palindrome exactly when it equals its own reverse. The counting function does not change at all — only the helper's inside does.
Time
O((high − low) · d)Space
O(1)Java
class Solution {
boolean isPalindrome(int n) {
int original = n;
int reversed = 0;
while (n > 0) {
reversed = reversed * 10 + n % 10;
n /= 10;
}
return reversed == original;
}
public int countPalindromes(int low, int high) {
int count = 0;
for (int n = low; n <= high; n++) {
if (isPalindrome(n)) {
count++;
}
}
return count;
}
}