Algorithm-Palindrome Number

Posted on

Description

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Examples

1
2
Input: -1
Output: false
1
2
Input: 101
Output: true
1
2
Input: 20
Output: false

Pseudocode

Actually, the first thought rising up in my mind was to convert the integer number into string, then compare the characters. However, there is a follow up requirement, which is Coud you solve it without converting the integer to a string?. Then I thought of another way: get each digit of the integer, store them into a array list, then compare these digits.

Implementation-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
import java.util.List;
import java.util.ArrayList;

public class Solution{
    public boolean isPalindrome(int x) {

        if(x < 0){
            return false;
        }
        if(x == 0) {
            return true;
        }
        // split each digit of the number x
        List<Integer> numberList = new ArrayList<>();
        int remainder = 0;
        int divideNumber = 10;
        for(;;){
            remainder = x % divideNumber;
            x = x / divideNumber;
            numberList.add(remainder);
            if(x == 0){
                break;
            }
        }
        // compare forward digits with backward digits
        boolean flag = true;
        for(int i=0, j= numberList.size() - 1; i < j; i++, j--){
            if(numberList.get(i) != numberList.get(j)){
                flag = false;
                break;
            }
        }
        return flag;
    }
}

Improved Implementation

The improved algorithm is from the online discussion. It is a little different from my solution but the general idea is the same. This implement directly calculate the reversed number of the original number, which makes the logic more clearly.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution{
    public boolean isPalindrome(int x) {
        int original = x;
        
        if(x < 0){
            return false;
        }
        
        int reverse = 0;
        while(x >= 1){
            int digit = x % 10;
            reverse = reverse * 10 + digit;
            x = x / 10;
        }
        
        if(reverse == original){
            return true;
        }else{
            return false;
        }
    }
}

References

Palindrome Numbers