Palindrome Number

easy Number Problems

Problem

A palindrome number reads the same from left to right and from right to left. Read an integer and print true if it is a palindrome, otherwise print false. Negative numbers are not palindromes.

Constraints

  • -10^15 <= n <= 10^15

Examples

Input

121

Output

true

Input

123

Output

false

Solutions

Best approachTime O(d)Space O(1)

We build the reverse of the number digit by digit and compare it with the original number. A negative number is never a palindrome.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Check if a number is a palindrome.
 * Input   : One integer.
 * Output  : true or false.
 * Approach: Reverse the digits and compare with the original.
 * Time    : O(d)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method receives a number and returns true if the number is a palindrome.
    static boolean isPalindrome(long number) {
        // Step 1: A negative number is not a palindrome because of the minus sign.
        if (number < 0) {
            return false;
        }

        // Step 2: Save the original number. We change "remaining" in the loop.
        long remaining = number;

        // Step 3: Build the reversed number. It starts at 0.
        long reversed = 0;

        // Step 4: Repeat until no digits are left.
        while (remaining > 0) {
            // Step 4a: Add the last digit to the end of the reversed number. Example: 12 -> 12 * 10 + 1 = 121.
            reversed = reversed * 10 + remaining % 10;

            // Step 4b: Remove the last digit. Example: 121 / 10 = 12.
            remaining = remaining / 10;
        }

        // Step 5: A palindrome is equal to its reverse.
        return reversed == number;
    }

    public static void main(String[] args) {
        long number = new Scanner(System.in).nextLong();
        System.out.println(isPalindrome(number));
    }
}
Hints (2)
  1. Which operator gives the last digit?
  2. Which operation removes the last digit?