Check if a Number Is a Palindrome
Solve this ProblemEasy10 min
Topics
BasicsLoopsMath
Companies
TCSInfosysWipro
Given a non-negative integer
n, return whether it reads the same forwards and backwards.
The full-reversalFull ReversalBuilding the completely reversed number (same technique as the Reverse a Number problem) and comparing it to the original. approach is the most direct way to think about it: reverse everything, then compare. The half-reversalHalf ReversalStopping the reversal loop halfway through, once n is no longer bigger than the reversed-so-far half, then comparing the two halves directly. approach does only as much work as is actually needed to answer the question — there's no point reversing the second half of the digits when they can just be compared against the first half directly as the loop goes.
Test Case 1:
Input:n = 121
Output:true
Explanation:121 reads the same forwards and backwards.
Test Case 2:
Input:n = 123
Output:false
Explanation:123 reversed is 321 — different.
Test Case 3:
Input:n = 10
Output:false
Explanation:10 reversed is 01, which as a number is 1 — not equal to 10.
Constraints
- ◆
0 ≤ n ≤ 1000000000
Try the Dry Run
Approach & Solutions
Reverse the Whole Number, Then CompareGood
Build the fully reversed number using the same digit-by-digit technique as the Reverse a Number problem, then compare it to the original. If they match, n is a palindrome.
Time
O(d) — d is the number of digitsSpace
O(1)Java
1class Solution {
2 public boolean isPalindromeNumber(int n) {
3 int original = n;
4 int reversed = 0;
5 while (n != 0) {
6 int digit = n % 10;
7 reversed = reversed * 10 + digit;
8 n = n / 10;
9 }
10 return reversed == original;
11 }
12}Reverse Only Half the DigitsOptimal
There's no need to reverse the entire number — only enough of it to compare against the half that's left. Keep reversing digits off of n into reversedHalf until n is no longer bigger than reversedHalf; at that point, either the two halves match exactly (even digit count), or the first half still has one extra middle digit that reversedHalf should drop before comparing (odd digit count). A number ending in 0 (other than 0 itself) can never be a palindrome, so that's ruled out upfront without even starting the loop.
Time
O(d)Space
O(1)Java
1class Solution {
2 public boolean isPalindromeNumber(int n) {
3 if (n < 0 || (n % 10 == 0 && n != 0)) {
4 return false;
5 }
6 int reversedHalf = 0;
7 while (n > reversedHalf) {
8 reversedHalf = reversedHalf * 10 + n % 10;
9 n = n / 10;
10 }
11 return n == reversedHalf || n == reversedHalf / 10;
12 }
13}