Palindrome Integer | InterviewBit | Solution Explained
Palindrome Integer is a very standard problem. I explain 2 solutions in both CPP and Python3. Problem Link.
0. Palindrome Integer: Problem Discussion
0.0. IO Format
- input:
- an integer in the standard range: -2^31 to 2^31-1
- output:
- 1 if the input is a palindromic number and 0 otherwise
Palindromic number: A number that can be read the same way forward and backward.
0.1. Examples
- 123 is not a palindrome
- 121 is a palindrome
- 123321 is a palindrome
- 12321 is a palindrome
1. Palindrome Integer: Complete Reversal Solution
Since the problem clearly mentions that we need to be able to read the solution both in forward and backward directions, won’t it be nice if we could reverse the digits of the number?
One way is to start a variable rev
with 0
and each time, extract one digit from the right side of A
. So, we extract digits from A’s end and add them at the end of rev
. This is a good time to whip out your notebook and actually try it out!
int Solution::isPalindrome(int A) { if (A < 0) return 0; if (A < 10) return 1; long long rev = 0; int A_copy = A; while (A) { rev = rev * 10 + (A % 10); A /= 10; } if (A_copy == rev) return 1; else return 0; }
class Solution: def isPalindrome(self, A): if A < 0: return 0 if A < 10: return 1 A_copy = A rev = 0 while A: rev = rev*10 + A%10 A //= 10 return int(A_copy == rev)
2. Palindrome Integer: Half Reversal
There is a small catch with the above solution. Note how I used long long int
instead of just int
in the CPP solution. That’s because if we have a large number like 1,999,999,999, when we reverse the digits, we get 9,999,999,991. This is above the integer limit!
To bypass this problem, we can stop the extraction of digits midway. The below logic indicates.
class Solution: def isPalindrome(self, A): if A < 0: return 0 if A < 10: return 1 rev = 0 while A > rev: rev = rev*10 + A % 10 A //= 10 if rev < 10: return int(rev == A) else: return int(rev == A or rev//10 == A)
Both work in O(1) time and space.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this