Palindrome Number – Solution & Complexity
Solution Walkthrough
Step 1: Handle Impossible Cases First
- Negative numbers are not palindromes because the minus sign appears only on the left.
- Positive numbers ending in
0cannot be palindromes unless the number itself is0. - These checks avoid extra work and prevent misleading reversals.
Step 2: Reverse Only Half of the Number
- Reversing the whole number works, but reversing half avoids unnecessary work and possible overflow in some languages.
- Repeatedly move the last digit of
xintoreversed_half. - Stop when
reversed_halfis greater than or equal to the remainingx.
Step 3: Compare Even and Odd Lengths
- For an even number of digits, the remaining left half should equal the reversed right half.
- For an odd number of digits, the middle digit is irrelevant.
- Dropping the middle digit with
reversed_half // 10handles odd lengths.
Step 4: Final Complete Solution
- The algorithm uses arithmetic only, so it satisfies the no-string follow-up.
- It processes about half the digits of the input.
- Time complexity is O(log10 n), and extra space complexity is O(1).
