Examples:
Input : x= 121
output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Input: x = 10
Output: false.
This challenge requires you to have an understanding of how math of integers work i.e. how to utilize division and module to solve this problem.
We can actually convert this number x into a string and then compare both strings to solve this challenge; however, there's a follow up question,
"Can we solve this without the use strings?"
Approach#1
In this approach, we are simply going to convert number x into a string from left to right and right to left. You can use standard library functions to convert a number to a string, but I strongly believe that this problem is designed to make programmers aware of the math behind converting a number to a string which is why I implemented my own toString() method.
There's no harm in using in-built helper functions; however, for the sake of learning, you should always try to implement a functionality yourself to unmask the logic behind how things work.
Let's suppose we have a number x=1221.
In theory, you can start with extracting the rightmost digit of the number using the modulo % operator which can be done by using the base 10.
When you perform x%10, It gives you the remainder of a number.
So if we perform 1221%10 = it will give us the right most number which is 1.
Once that number is extracted, we don't need that right most digit. We can discard it by using the integer division, x/10. Once you divide 1221/10, we will get 122.
So steps can be written like this:
- x=1221.
- get the right most digit --> 1221%10 = 1
- discard the right most digit --> 1221/10 = 122
- x=122
- get the right most digit --> 122%10= 2
- discard the right most digit --> 122/10= 12
- x=12
- get the right most digit --> 12%10= 2
- discard the right most digit --> 12/10 = 1
- x=1
- get the right most digit --> 1%10 = 1
- discard the right most digit --> 1/10 = 0
- x=0, then we know there's no more number left so we can stop the iteration process.
So as you can see we extracted 1,2,2,1 from step 1 to 4 as we kept shrinking down the x. Once you understand this math, that's the underlaying challenge of this problem that we need to learn about.
Now only one important thing to understand is how to add a single digit integer into a string? The answer is char.
char is needed to convert digits into a string because characters are the building blocks of strings. When we perform arithmetic operations on integers, the result is a numeric value.To convert this numeric value to its corresponding character representation, we need to add it to the ASCII value of the character '0'; It's called character encoding.
ASCII value of '0' is 48, 1-49,2-50, and so on.
char digit = '0' + number; // 48+5 = 53 = 5; so the number is 5.A few helpful ASCII value starters : 0 - 48, A-65, a-97Important : You cannot convert a big number 2 digits number therefore we must perform % and / operations to separate digits and then convert it into a string.
Implementation
string numberToString(int x){
string str;
bool isNegative=false;
if(x == 0) {
//edge case when you are trying to convert number into a string.
str = "0";
}
if(x < 0){
isNegative=true;
x = -x;
}
//STEPS ARE Performed here. Loop will continue until X hits 0.
while(x > 0){
char digit = '0'+ x%10; //STEP 1 - extract the right most digit
str += digit;
x /= 10; // Shrink the X, discarding the right most digit.
}
if(isNegative){
str = '-' + str;
}
return str;
}
In above code, I am iterating through exact steps that we used for the number = 1221. Please read my comments in the code to understand a bit better. I also added code to handle input of X being 0 because while loop doesn't work if x=0.Once you convert this number to a string, we can reverse this string by iterating through each character which can easily be done by a for loop. If you convert the string "1221" and reverse it, then it will "1221" which means it is a palindrome number.
Finally, we can just compare two strings using == operator to return true or false value to answer correctly. You can check the full source code here --> IsPalindromeUsingStrings.cpp
Approach#2
So the follow up question of this challenge was to solve this challenge without converting a number into a string. There are more than a few ways to solve this using math, but here I will explain only one way. I will mention the other ways.
Now, if X= 1221.
Then we know that we can perform 1221%10 to get right most digit. What if we want to get right most 2?
We can simply do that by 1221%100, which will give us the second digit from the right side.
So one way to solve this challenge is by comparing first and last digit, and moving inwards.
Steps can be written as follows:
- Find the base of 10 division number to get first digit.
- x=1221 so to get the first digit we have to divide it by 1000.
- x=123 then we have to divide by 100.
- x=112211 then we have to divide by 100000.
- So if x=1221 and base division is 1000.
- compare x%10 == x/div
- 1221%10 = 1 (x%10)
- 1221/1000 = 1 (x/div)
- 1==1? TRUE.
- it is palindrome and continue.
- Remove/Reset first and last digit now from the number X.
- (x%div) 1221%1000 = 221 (removed first)
- 221/10 = 22 (removed last digit)
- X=22.
- base division is 10 now for 22 so we can reset div.
- div =div/100. (100 because we removed 2 digits)
- 1000/100 = 10
- div =10
- X = 22, div = 10 now.
- compare x%10 == x/div (get first and last digit of x)
- 22%10 = 2
- 22/10 = 2
- (22%10 == 22/10) = True
- It is palindrome and continue eliminating first and last digit.
- Remove/reset first and last digit.
- (x%DIV) = 22% 10, x becomes 2
- x/10 = 22/10 , x becomes 0 (No more digits left)
- x=0 which will be the indicator to stop the loop.
So above steps would look as follows in code.
bool isPalindromeByDivision(int number){
if(number < 0 || number != 0 && number%10 == 0)
return false;
int div = 1;
while(number >= 10*div){
div *= 10; //To find base of 10 in order to get first digit.
}
while(number > 0) {
if(number % 10 != number / div)
return false;
number = (number%div) / 10;
// (n%div) gives us remainder. essentially getting remainder and then dividing to discard the last digit
div /= 100; //Reset div because we removed 2 digits from number.
}
return true;
}
This is a very efficient way of solving this challenge. I am also eliminating obvious numbers that cannot be palindrome by adding this condition:
if(number < 0 || number != 0 && number%10 == 0)
return false;
When x < 0, for example, x= -121, then this number cannot be palindrome because reverse number would be 121- which is why you can directly return false when x is less than 0.Another condition is the important one. Integers aren't preceded by 0 like 0121. They can be written as 121 only, so by checking x%10 == 0 then we can directly return false because those numbers cannot be palindrome. You can run the following code to test this condition.
//Run this to test.
void experimentProof()
{
for (int i = 1; i <= 1000; i++)
{
if (i % 10 == 0)
{
cout << i << " is divided by 10 so cannot be palindrome!" << endl;
}
}
//basicall x%10 == 0 -> means that if last digit of a number is 0 then it cannot be palindrom
// because positive numbers don't have leading 0s.
//120 - last digit can be found by 120%10=0 which means it cannot be palindrome.
}
There are other ways to solve this problem and I have coded them in my source code, you can check it here --> PalindromeWithoutStrings.cppI hope that shed some light on the understanding of how to solve this problem. As always, first try to solve a problem by yourself. This problem difficulty is medium and I personally had to look up for methods to extract and add numbers to perform reverse addition. The above solution is really simple, elegant and efficient because we are simply comparing first and last digits. It will not iterate through whole number to get the final decision.
If you find any problem with the code I posted, feel free to comment and suggest correction.
0 Comments