LC 9. Palindrome Number

The problem

First Solution

I'll keep this one short and sweet. Here, convert to a string and check if the reversed version is equal to the original. To reverse, the string is split to an array, reversed, then rejoined as a new string.

Edit (8/14/2024): It has been a few months since I've solved this, but now that I've learned more algorithmic techniques and have started learning C++, I came back for another go. This time, I took a two pointers approach. This is better than my original TypeScript solution but still isn't optimal. I didn't really care about the mathematical solution so much as I intended on practicing two pointers and C++ standard library basics. I'll include the math one though which is better because it avoids the string conversion altogether.

function isPalindrome(x: number): boolean {
  return x.toString() === x.toString().split('').reverse().join('')
}

Optimal Solution in C++ - $O(n)$ Time

This solution works by mathematically reversing the integer using modulo. This avoids the need to convert to a string or split, reverse, and rejoin the to find if they're equal. On each iteration of the while loop the rightmost number is retrieved using modulo. It is then added to a reversed number. On all subsequent iterations the number just added will be multiplied by 10 which moves it to the left, reversed position. The only confusing bit has to do with the /= operator. By doing this, it removes the number retrieved with the modulo because the reversed is a long long which causes the decimal to be dropped. If it were a float, the decimals would be allowed and xCopy would never go to 0 for the while loop to end.

bool isPalindrome(int x) {
  if (x >= 0) {
    long long reversed = 0;
    long long xCopy = x;
    while (xCopy != 0) {
      int firstDigit = xCopy % 10;
      reversed = (reversed * 10) + firstDigit;
      xCopy /= 10;
    }
    return reversed == x;
  }
  return false;
}