Where does Leetcode get its questions from

Determines whether an integer is the number of palindromes. The number of palindromes refers to integers that are read in the same order (left to right) and backwards (right to left).

Can you solve this problem without converting integers to strings?

solution


Method: Reverse Half Number

Ideas

The first idea that came to mind was to convert a number to a string and see if the string is a palindrome. However, this requires additional non-constant space to create strings that are not allowed in the problem description.

The second idea is to invert the number itself and then compare the inverted number to the original number. If they are the same, the number is a palindrome. However, if the inverted number is greater than int.MAX \ text {int.MAX} int.MAX, problems with integer overflows occur.

To avoid the possible overflow problem that arises from inverting the number, after the second consideration you should consider inverting only half of the int \ text {int} int number. If the number is a palindrome, the second half of the number after inverting should be the same as the first half of the original number.

For example, enterWe can put the number "12"21The second half of "21"Inverted to"12"And compare it to the first half of" 12 "because they are the same and we know Is a palindrome.

Let's see how to turn this idea into an algorithm.

algorithm

First we should deal with some critical cases. All negative numbers cannot be palindromes, for example: -123 is not a palindrome because it is not the same. So we can return false for all negative numbers.

Now let's see how you can reverse the numbers in the second half. For numbers, when run, and we will get the last digit, To get the penultimate digit, we can first remove the last digit from dividing, then find the remainder of the result of the previous step divided by 10., you can get the penultimate digit. If we multiply the last digit by 10 and add the penultimate digit, and we get the number we want to reverse. If we continue this process, we will get more inverted digits.

The question is, how do we know that the number of digits in the inverted number has reached half the number of digits in the original number?

We divide the original number by 10, then multiply the inverted number by 10. If the original number is less than the inverted number, it means we have processed half of the digits.

Complexity analysis

  • Time complexity: O (log10 (n)) O (\ log_ {10} (n)) O (log 10 (n)), for each iteration we divide the input by 10 so the time is complicated The degree is O ( log10 (n)) O (\ log_ {10} (n)) O (log 10 (n)).
  • Spatial complexity: O (1) O (1) O (1).