[Toggle Comments]
package main // file: impl-002.go // Revert half of the number and check if it matches the second half. // (we divide the input by 10 at every iteration) // // time: O(log(N)) (where N is the input number); space: O(1) func isPalindromeRevert(x int) bool { if x == 0 { return true } if x < 0 { // Negative number cannot be a palindrome. return false } if x%10 == 0 { // `10` backwards is `01` which is `1` ∴ not palindrome return false } // Each step we multiply `reverted` by 10 and divide `x` by 10. // // If the number has an even number of digits and is a palindrome, // then `leftHalf` will eventually be equal to `reverted` and the loop // will exit (at [4]). // (take 4224; when the loop exits, `leftHalf` will be 42 // and `reverted` will be 42 too.) // // If the number has an odd number of digits and is a palindrome — [1], // then when the loop exits, `reverted` will have one extra digit/ // (take 12321; when the loop exits, `leftHalf` will be 12, // and `reverted` will be 123). // In that case, we can discard the least significant digit of `reverted` // and match the rest. If they match, we have a palindrome number. // (i.e., `reverted` becomes 12 instead of 123; we remove the ones digit // “3”. Since now `reverted` (12) is equal to `leftHalf` (12), we have a // palindrome number. — That is taken care of at [9].) // // Now, let’s look at the possible fail cases: // // If the number has an even number of digits and is **not** a // palindrome — [2], // the for loop will either end with `leftHalf` and `reverted` having // the same number of digits, but different in values — [3]; // or `reverted` will be two digits longer than `leftHalf` — [4]. // (for [3]: 1443 -> leftHalf: 14; reverted: 34 // for [4]: 1412 -> leftHalf: 1; reverted: 214) // // We’ll reach half of the number (give or take a digit) once `leftHalf` // is less than or equal to `reverted`. // // Finally, if the number has an odd number of digits and is **not** a // palindrome — [5], // then we’ll end up something similar to [1], but the final // `leftHalf` and `reverted` will not be equal. // (e.g., 12342; reverted: 243 -> 24, leftHalf: 12; 12 != 24) reverted := 0 leftHalf := x for leftHalf > reverted { lastDigit := leftHalf % 10 reverted = reverted*10 + lastDigit leftHalf = leftHalf / 10 if leftHalf == reverted { // Palindrome with even number of digits. return true // — [4] } } // When we reach here, x may have… // // * An even number of digits and is not a palindrome // (see [3] and [4]). — [6] // * An odd number of digits and is not a palindrome // (see [5]). — [7] // * An odd number of digits and is a palindrome // (see [1]). — [8] // // The “even number of digits and is a palindrome” case has an early // exit at [4], so we don’t handle it here. // // For [6], [9] will always be `false`, which we want because we want // a non-palindrome check to return `false`. // (See the explanations in [3] and [4].) // // For [7], [9] will always be `false`. Again we want this because it’s // a non-palindrome case, and we’d like the check to return `false`. // (See the explanation in [5].) // // For [8], [9] will always be true. We do want this too, since `x` is a // palindrome number in this case, and we want to return `true` when // that happens. // (See the explanation in [1].) // // Those are all the cases that can happen. Therefore, the below // return expression (along with [4]) always gives what we need. return leftHalf == reverted/10 // — [9] } /* * \ * \\, * \\\,^,.,,. Zero to Hero * ,;7~((\))`;;,, <zerotohero.dev> * ,(@') ;)`))\;;', stay up to date, be curious: learn * ) . ),(( ))\;, * /;`,,/7),)) )) )\,, * (& )` (,((,((;( ))\, */