Problem

Given A and B, count the numbers N such that A ≤ N ≤ B and N is a

palindrome.Input:

First line contains T, the number of testcases. Each testcase consists

of two integers A and B in one line.Output:

For each testcase, print the required answer in one line.

Constraints:

1 ≤ T ≤ 10

0 ≤ A ≤ B ≤ 10^5

```
private static boolean[] isPalindrome = isPalindrome();
public static void main(String args[] ) throws NumberFormatException,
IOException{
BufferedReader reader = new BufferedReader(new InputStreamReader(
System.in));
int totalTestCase = Integer.parseInt(reader.readLine());
StringBuilder outputPalindromeCount = new StringBuilder();
for (int i = 0; i < totalTestCase; i++) {
String[] input=reader.readLine().split(" ");
int startNo = Integer.parseInt(input[0]);
int endNo = Integer.parseInt(input[1]);
int totalFoundPalindrome = getPalindromeCount(startNo, endNo);
outputPalindromeCount.append(totalFoundPalindrome + "n");
}
System.out.println(outputPalindromeCount);
}
private static int getPalindromeCount(int startNo, int endNo) {
int totalPalindromeFound = 0;
for (int i = startNo; i <= endNo ; i++ ){
if(isPalindrome[i]){
totalPalindromeFound++;
}
}
return totalPalindromeFound;
}
private static boolean[] isPalindrome() {
boolean[] isPalindrome = new boolean[100001];
Arrays.fill(isPalindrome, 0, 10, true);
for (int i = 10; i <= 100000; i++) {
if (checkForPalindrome(i)) {
isPalindrome[i] = true;
}
}
return isPalindrome;
}
private static boolean checkForPalindrome(int i) {
int divNo = 1;
while (i / divNo >= 10) {
divNo = divNo * 10;
}
while (i != 0) {
int startingDigit = i / divNo;
int lastDigit = i % 10;
if (startingDigit != lastDigit) {
return false;
}
i = (i % divNo) / 10;
divNo = divNo / 100;
}
return true;
}
}
```

For this input:

```
``````
6
0 0
1 1
1 10
1 9
1 1000
1000 100000
```

this code took 0.18 seconds. It’s taking almost 0.18-0.20 seconds for various sets of input (link of all inputs and time).

What are the other Efficient way of checking palindromes (not just a way of conversion to a string and then check but really efficient)?

How could have I optimized the above code further (apart from `BitSet`

which is a trade off for runtime)?

Solution

`isPalindrome`

is a very unfortunate name in this code:

- Names starting with “is” are typically methods returning a simple
`boolean`

- … but in this code
`isPalindrome`

is a parameterless method returning a`boolean`

*array* - … and at the same time there is also a
`boolean`

array called`isPalindrome`

It would be better to use different names for the method and the array,

and neither should start with the word “is”.

In the `isPalindrome`

method, you could shorten this:

```
``````
if (checkForPalindrome(i)) {
isPalindrome[i] = true;
}
```

to this:

```
isPalindrome[i] = checkForPalindrome(i);
```

I’m a big fan of descriptive variable names,

but I think you went a bit overboard, for example here:

```
``````
private static int getPalindromeCount(int startNo, int endNo) {
int totalPalindromeFound = 0;
for (int i = startNo; i <= endNo ; i++ ){
if(isPalindrome[i]){
totalPalindromeFound++;
}
}
return totalPalindromeFound;
}
```

I would simplify some of the names there to:

```
private static int getPalindromeCount(int start, int end) {
int palindromeCount = 0;
for (int i = start; i <= end; i++) {
if (isPalindrome[i]) {
palindromeCount++;
}
}
return palindromeCount;
}
```

The numbers 100001 and 100000 are *magic*.

It would be good to create a constant from 100000 with a descriptive name.

A small tip: it’s a lot easier to parse simple input using a `Scanner`

, with its `nextInt`

and `nextLine`

methods,

instead of a `BufferedReader`

and `Integer.parseInt`

.

Also, why build output in a `StringBuilder`

if you will print its contents anyway inside the same method.

You could just print the results directly.

```
``````
int divNo = 1;
while (i / divNo >= 10) {
divNo = divNo * 10;
}
while (i != 0) {
int startingDigit = i / divNo;
int lastDigit = i % 10;
if (startingDigit != lastDigit) {
return false;
}
i = (i % divNo) / 10;
divNo = divNo / 100;
}
```

This seems more complicated than it needs to be. First you are finding the location of the first digit. Then you go through digit by digit. Why not do both at once and get rid of `divNo`

?

```
private static boolean isPalindrome(int left) {
// a trailing zero is impossible to match
if (left % BASE == 0) {
// only a literal 0 will work
return left == 0;
}
int right = 0;
while (left > right) {
int currentDigit = left % BASE;
left /= BASE;
// if there are an odd number of digits,
// and the left half of the number equals the reversed right half,
// it's a palindrome
if (left == right) {
return true;
}
// reverse the right half, assuming no trailing zeroes
right = BASE * right + currentDigit;
}
// if there are an even number of digits
return left == right;
}
```

Note that I also renamed `isPalindrome`

to `generatePalindromes`

and `checkPalindrome`

to `isPalindrome`

. And I added a constant to replace the magic number `10`

. Algorithm explained inline with comments.