Palindrome Numbers
A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam and 121.
One of Leet Code’s easy problem’s involves coding a solution to determine whether an integer is a palindrome. The caveat being integer to string conversion is not allowed.
To understand this problem, here are a few test case. The integer 121 reversed is 121 thus true, 123 reversed is 321 thus false ,-123 reverse is 321- is false and 10 reversed is 01 as an integer is 1 thus false.
This results in a few special cases that we can remove from our problem set, all negative numbers and any multiple of ten are not palindromes.
Cracking on to my solution, my initial thoughts was to split the number into an array and reverse the array and finally comparing the two arrays. In this approach, the length of the number is required. To calculate the length of an integer we could use a logarithmic approach.
int length = (int) (Math.log10(number) + 1);
However, something to note is that log base 10 of 0 of any number is not defined. In this case zero is a special case and is a palindrome thus I handled this check by not getting into this part of the code if the integer provided is zero.Thereafter, I initialized two empty arrays of size length.
Splitting the integer involved looping the over the length and performing a division and modulus operation to get the digit in a particular position. For example, for an integer 123, to get the digit at the last position, which is index 2, divide the number by 10 to the power of the loop start index. This results in the original number. Performing a modulus operation on the result with 10 and the result is the number in the last position. To illustrate this using the table below the number is reversed and I store the result in the reversed array.
+------------+----------------------+--------------+--------+
| Loop Index | Division | Modulus | Result |
+------------+----------------------+--------------+--------+
| 0 | 123 / 10 ^ (0) = 123 | 123 % 10 = 3 | 3 |
+------------+----------------------+--------------+--------+
| 1 | 123 / 10 ^ (1) = 12 | 12 % 10 = 2 | 2 |
+------------+----------------------+--------------+--------+
| 2 | 123 / 10 ^ (2) = 1 | 1 % 10 = 1 | 1 |
+------------+----------------------+--------------+--------+Looping through the reversed array and storing the reversed values in a different array, resulted in having two arrays one with the the integer split in it’s current order and the other in reverse order. Comparing both arrays determines if the integer is a palindrome or not.
Reading through the Leet Code’s solution, the approach is quite different. The premise is for an integer to be a palindrome only the first half should be equal to the reversed second half. For example, 1221, first half 12 will be equal to reversed second half 21 reversed is 12 thus the number is a palindrome. This logic also prevents overflow issues as only half the length of the integer is required. Wondering about numbers with an odd number of digits, that will also be handled.
Splitting the number in this approach involves division and modulus operation as well the goal being to reverse the last half of an integer.
The logic involves getting the last digit from a number and subsequently removing it from the original number thus getting the next last digit. To add to the reversed digit the current reversed digit is multiplied by ten creating a place value for the current last digit. Finally, adding the current last digit to the last place value results in the reversed number as illustrated below.
+-----------------+---------------+-----------------+
| Number | Last digit | Reversed |
+-----------------+---------------+-----------------+
| 1221 | | 0 |
+-----------------+---------------+-----------------+
| 1221 | 1221 % 10 = 1 | 0 * 10 + 1 = 1 |
+-----------------+---------------+-----------------+
| 1221 / 10 = 122 | 122 % 10 = 2 | 1 * 10 + 2 = 12 |
+-----------------+---------------+-----------------+
| 122 / 10 = 12 | | |
+-----------------+---------------+-----------------+The stopping condition for this approach, is when the reversed digit is greater than the number. Since once the reversed number is larger than the original number we looped through half of the digits.
For odd numbers, a simple solution applies. In a palindrome the middle number does not change positions when the number is reversed. Therefore, it can be ignored by removing it from the reversed number we form. This is because the middle number will be added to the last place of our reversed number. To remove it we simply divide the reversed number by ten. For example the number 12321 results in the reversed number 123 and the current number as 12. Dividing 123 by 10 removes the last digit resulting in 12.
+-------------------+----------------+-------------------+
| Number | Last digit | Reversed |
+-------------------+----------------+-------------------+
| 12321 | | 0 |
+-------------------+----------------+-------------------+
| 12321 | 12321 % 10 = 1 | 0 * 10 + 1 = 1 |
+-------------------+----------------+-------------------+
| 12321 / 10 = 1232 | 1232 % 10 = 2 | 1 * 10 + 2 = 12 |
+-------------------+----------------+-------------------+
| 1232 / 10 = 123 | 123 % 10 = 3 | 12 * 10 + 3 = 123 |
+-------------------+----------------+-------------------+
| 123 / 10 = 12 | | |
+-------------------+----------------+-------------------+The solution for this approach is of the space complexity: O(1) and the time complexity O(log10(n)).
