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.
Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.
Recommended Posts
Gas Station | InterviewBit | Solution Explained
June 13, 2022
Majority Element | InterviewBit | Solution Explained
June 13, 2022
Comments
Leave a Reply
This site uses Akismet to reduce spam. Learn how your comment data is processed.
Please write the proof.
This solution need an amendment for 2 digit number.
Please write a Proof for this
Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.
A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.
Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.
To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.
Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.
This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.
Understanding why solar energy consultants assist clients via Matthew D’Agati.
Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8