All code here is in Javascript!
Recently I came across a small code challenge that I had a good time solving. It's not that the question itself is difficult to solve, it's that I had to rethink the way I would solve it compared to similar solutions I have given in the past. The question was "Write a function to determine whether a given number is a palindrome. You cannot covert the number to a string to do this."
Now, I have solved this problem in the past by converting it to a string and iterating over the results. It's a pretty simple solution, but when not allowed to cast the int it becomes a bit more difficult to reason through. This question is less of a test of whether you can identify a palindrome and more of a test of whether or not you understand how logarithms and the modulo operator work. Still, it was a fun challenge, so let's walk through the way I solved it!
First, the problem stated that negative numbers cannot be palindromes, so that gives us a great spot to start our code.
const isPalindrome = x => {
if (x < 0) return false;
}
The first major task in this challenge is to figure out how many digits your number is. Integers, unlike their string counter parts, do not expose the idea of digits or length as a property so we must find our own way to figure this out. This is where logarithms come into play. To figure out the amount of digits we have, we want to find the base 10 logarithm of our number. This will give us a number that will produce our original number when set as the exponent of 10. We then floor the result and add one to get our digits.
const digits = Math.floor(Math.log10(x)) + 1;
The basics of this problem are that we want to compare two digits, the tens digit and the left most digit for whatever number is put in. We will do this with two operators: division and modulo. Division will grab things to the left of the decimal, modulo to the right. To grab our left most digit, we generate a number mask that we can use to divide our given number by to isolate the furthest digit. Basically, we need the smallest number possible number at the given number of digits (10, 1,000, 10,000, etc.)
const mask = Math.pow(10, digits - 1);
We then use the mask to grab the desired digits, and compare.
const getFirstAndLast = ({ x, mask }) => [parseInt(x/mask), x % 10];
const [highestDigit, onesDigit] = getFirstAndLast({ x, mask })
if (highestDigit !== onesDigit) return false;
Since I decided to take a recursive solution to this problem, the final step is to generate a new version of our number and call it again. We simply need to "cut off" the left most and tens digits of our number. Once again, much easier with strings since they support indexing, but not impossible with numbers either. We use our mask with the modulo operator to remove the left most digit, divide by 10 and floor to remove the tens digit and we are good.
const newNum = Math.floor((x % mask)/10)
return isPalindrome(newNum);
It was a fun problem to solve! Definitely pushed me to think differently than I normally would, this problem is a lot easier if you can convert it to string but it was fun doing it this way. This would also have the benefit of being more memory friendly since you don't have to store a bunch of immutable strings, you just operate on the ints themselves. Thanks for reading! Full code below.
const getFirstAndLast = ({ x, mask }) => [parseInt(x/mask), x % 10];
const isPalindrome = x => {
if (x < 0) return false;
const logged = Math.log10(x);
const digits = Math.floor(logged) + 1;
if (digits === 1 || x === 0) return true;
const mask = Math.pow(10, digits - 1);
const [highestDigit, onesDigit] = getFirstAndLast({ x, mask })
if (highestDigit !== onesDigit) return false;
const newNum = Math.floor((x % mask)/10)
return isPalindrome(newNum);
}