Jobs

Interviews

Discussions

Palindrome Number #9 Most Asked

Easy

Microsoft

18 views

Topics:

Two Pointers

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

-2³¹ <= x <= 2³¹ - 1

Follow up: Could you solve it without converting the integer to a string?

Try coding it in LeetCode

Palindrome Number #9 Most Asked

Easy

Microsoft

18 views

Topics:

Two Pointers

Given an integer x, return true if x is a palindrome, and false otherwise.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

-2³¹ <= x <= 2³¹ - 1

Follow up: Could you solve it without converting the integer to a string?

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Does the input integer `x` fit within a standard integer data type, or could it be a very large number that exceeds standard limits?
How should we handle negative numbers? For example, is -121 considered a palindrome?
Should we consider a single-digit number, like 5, to be a palindrome?
Is the input `x` guaranteed to be an integer, or could it be a non-integer type like a float or a string that needs to be handled?
Are there any constraints on solving this without converting the integer to a string?

Brute Force Solution

Approach

The most straightforward way to see if a number is a palindrome is to first figure out what the number looks like when its digits are written in reverse order. Then, you simply compare this new reversed number to the original one.

Here's how the algorithm would work step-by-step:

First, take the original number and set it aside so you don't lose it.
Next, figure out how to write the number backward. You can do this by taking the last digit of the original number and making it the first digit of a new number, then taking the second-to-last digit and making it the second digit, and so on, until you've used all the digits.
Once you have the completely reversed number, compare it to the original number you set aside at the beginning.
If the reversed number is exactly the same as the original number, then you've confirmed it's a palindrome.
If they are different in any way, it's not a palindrome.

Code Implementation

class Solution:
    def isPalindrome(self, original_number: int) -> bool:
        # A negative number cannot be a palindrome because the minus sign breaks the symmetry.

        if original_number < 0:
            return False

        number_to_reverse = original_number
        reversed_number = 0

        # Reverse the number by repeatedly taking the last digit and adding it to the new number.

        while number_to_reverse > 0:
            last_digit = number_to_reverse % 10
            reversed_number = (reversed_number * 10) + last_digit
            number_to_reverse = number_to_reverse // 10

        # The number is a palindrome if its reversed form is identical to the original.

        return original_number == reversed_number

Big(O) Analysis

Time Complexity

O(log n) – The time complexity is determined by the number of digits in the input integer, n. To reverse the number, we repeatedly perform division and modulo operations to extract the last digit and build the reversed number. The number of such operations is directly proportional to the number of digits in n, which is mathematically represented as log base 10 of n. Since the base of the logarithm does not affect the Big O notation, this process simplifies to O(log n).

Space Complexity

O(1) – The algorithm's space usage is constant because it only requires a few variables to store numbers, such as the original number, the reversed number, and the current digit. The amount of memory needed for these variables does not increase as the number of digits in the input number N grows. Since no data structures that scale with the input size are created, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The core idea is to reverse only half of the number and then compare it to the other half. This avoids dealing with the whole number at once and sidesteps potential issues with very large numbers.

Here's how the algorithm would work step-by-step:

First, handle some quick edge cases: negative numbers aren't palindromes, and any number ending in zero (except for zero itself) also can't be one.
Imagine you have the number. Start building a new number by taking the last digit from the original and placing it at the front of your new number.
As you take a digit from the original number, remove it.
Keep doing this—taking the last digit from the original and adding it to the new one—until the original number becomes smaller than or equal to the new number you're building.
At this point, you've essentially processed half of the digits.
Now, compare the remaining original number (the first half) with the new number you built (the reversed second half).
If they are the same, the number is a palindrome. If the original number had an odd number of digits, the middle digit will be left on the reversed half, so you just need to ignore that last digit on the reversed half before comparing.

Code Implementation

def is_palindrome(input_number):
    # Negative numbers cannot be palindromes. Also, if a number ends in 0 (and is not 0 itself),
    # its reverse would start with 0, so it can't be a palindrome.
    if input_number < 0 or (input_number % 10 == 0 and input_number != 0):
        return False

    reverted_second_half = 0
    remaining_first_half = input_number

    # We only need to reverse half the number to avoid potential integer overflow and improve performance.
    while remaining_first_half > reverted_second_half:
        last_digit = remaining_first_half % 10
        reverted_second_half = reverted_second_half * 10 + last_digit
        remaining_first_half //= 10

    # For numbers with an odd number of digits, the middle digit will be the last digit of the
    # reverted half. We can remove it by integer division as it doesn't affect the palindrome check.
    return remaining_first_half == reverted_second_half or remaining_first_half == reverted_second_half // 10

Big(O) Analysis

Time Complexity

O(log10(n)) – The complexity is determined by the number of digits in the input integer, which we can call 'n'. The solution's core logic is a single while loop that processes the number by repeatedly dividing it by 10. This division effectively removes one digit in each iteration. The loop runs until half of the digits are processed. Therefore, the number of operations is proportional to the number of digits in n, which is mathematically represented as log base 10 of n. This means the total operations approximate log10(n) / 2, which simplifies to O(log10(n)).

Space Complexity

O(1) – The algorithm uses a fixed number of integer variables to store the reversed half of the number and for intermediate calculations. This memory usage does not scale with the number of digits in the input integer, N. Because the amount of auxiliary space required is constant regardless of the input's size, the space complexity is constant.

Edge Cases

Case	How to Handle
Negative numbers (e.g., -121)	Negative numbers are never palindromes because the negative sign breaks the symmetry, so the function should return false immediately.
Single-digit numbers (0-9)	Single-digit numbers are always palindromes, and the algorithm correctly handles this by reversing the number to itself.
Numbers ending in zero (e.g., 10, 120)	If a positive number ends in zero, it cannot be a palindrome (except for 0 itself), so we can return false early.
The number is exactly zero	Zero is a palindrome, and the logic correctly handles this by returning true as it's a single-digit number.
The number is the maximum integer value (e.g., 2^31 - 1)	Reversing a large number like the max integer value can cause an integer overflow, which must be prevented by using a 64-bit integer for the reversed number or by reversing only half the number.
A number with an even number of digits (e.g., 1221)	The half-reversal approach works correctly by comparing the first half with the reversed second half when both halves are equal.
A number with an odd number of digits (e.g., 12321)	The half-reversal approach handles this by comparing the first half with the reversed second half after removing the middle digit.
The input is not a valid integer (e.g., null, undefined, string)	Depending on language and constraints, the solution might throw a type error or require explicit type checking at the beginning.

Negative numbers (e.g., -121)

How to Handle:

Negative numbers are never palindromes because the negative sign breaks the symmetry, so the function should return false immediately.

Single-digit numbers (0-9)

How to Handle:

Single-digit numbers are always palindromes, and the algorithm correctly handles this by reversing the number to itself.

Numbers ending in zero (e.g., 10, 120)

How to Handle:

If a positive number ends in zero, it cannot be a palindrome (except for 0 itself), so we can return false early.

The number is exactly zero

How to Handle:

Zero is a palindrome, and the logic correctly handles this by returning true as it's a single-digit number.

The number is the maximum integer value (e.g., 2^31 - 1)

How to Handle:

Reversing a large number like the max integer value can cause an integer overflow, which must be prevented by using a 64-bit integer for the reversed number or by reversing only half the number.

A number with an even number of digits (e.g., 1221)

How to Handle:

The half-reversal approach works correctly by comparing the first half with the reversed second half when both halves are equal.

A number with an odd number of digits (e.g., 12321)

How to Handle:

The half-reversal approach handles this by comparing the first half with the reversed second half after removing the middle digit.

The input is not a valid integer (e.g., null, undefined, string)

How to Handle:

Depending on language and constraints, the solution might throw a type error or require explicit type checking at the beginning.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Does the input integer `x` fit within a standard integer data type, or could it be a very large number that exceeds standard limits?
How should we handle negative numbers? For example, is -121 considered a palindrome?
Should we consider a single-digit number, like 5, to be a palindrome?
Is the input `x` guaranteed to be an integer, or could it be a non-integer type like a float or a string that needs to be handled?
Are there any constraints on solving this without converting the integer to a string?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, take the original number and set it aside so you don't lose it.
Next, figure out how to write the number backward. You can do this by taking the last digit of the original number and making it the first digit of a new number, then taking the second-to-last digit and making it the second digit, and so on, until you've used all the digits.
Once you have the completely reversed number, compare it to the original number you set aside at the beginning.
If the reversed number is exactly the same as the original number, then you've confirmed it's a palindrome.
If they are different in any way, it's not a palindrome.

Code Implementation

class Solution:
    def isPalindrome(self, original_number: int) -> bool:
        # A negative number cannot be a palindrome because the minus sign breaks the symmetry.

        if original_number < 0:
            return False

        number_to_reverse = original_number
        reversed_number = 0

        # Reverse the number by repeatedly taking the last digit and adding it to the new number.

        while number_to_reverse > 0:
            last_digit = number_to_reverse % 10
            reversed_number = (reversed_number * 10) + last_digit
            number_to_reverse = number_to_reverse // 10

        # The number is a palindrome if its reversed form is identical to the original.

        return original_number == reversed_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The core idea is to reverse only half of the number and then compare it to the other half. This avoids dealing with the whole number at once and sidesteps potential issues with very large numbers.

Here's how the algorithm would work step-by-step:

First, handle some quick edge cases: negative numbers aren't palindromes, and any number ending in zero (except for zero itself) also can't be one.
Imagine you have the number. Start building a new number by taking the last digit from the original and placing it at the front of your new number.
As you take a digit from the original number, remove it.
Keep doing this—taking the last digit from the original and adding it to the new one—until the original number becomes smaller than or equal to the new number you're building.
At this point, you've essentially processed half of the digits.
Now, compare the remaining original number (the first half) with the new number you built (the reversed second half).
If they are the same, the number is a palindrome. If the original number had an odd number of digits, the middle digit will be left on the reversed half, so you just need to ignore that last digit on the reversed half before comparing.

Code Implementation

def is_palindrome(input_number):
    # Negative numbers cannot be palindromes. Also, if a number ends in 0 (and is not 0 itself),
    # its reverse would start with 0, so it can't be a palindrome.
    if input_number < 0 or (input_number % 10 == 0 and input_number != 0):
        return False

    reverted_second_half = 0
    remaining_first_half = input_number

    # We only need to reverse half the number to avoid potential integer overflow and improve performance.
    while remaining_first_half > reverted_second_half:
        last_digit = remaining_first_half % 10
        reverted_second_half = reverted_second_half * 10 + last_digit
        remaining_first_half //= 10

    # For numbers with an odd number of digits, the middle digit will be the last digit of the
    # reverted half. We can remove it by integer division as it doesn't affect the palindrome check.
    return remaining_first_half == reverted_second_half or remaining_first_half == reverted_second_half // 10

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Negative numbers (e.g., -121)	Negative numbers are never palindromes because the negative sign breaks the symmetry, so the function should return false immediately.
Single-digit numbers (0-9)	Single-digit numbers are always palindromes, and the algorithm correctly handles this by reversing the number to itself.
Numbers ending in zero (e.g., 10, 120)	If a positive number ends in zero, it cannot be a palindrome (except for 0 itself), so we can return false early.
The number is exactly zero	Zero is a palindrome, and the logic correctly handles this by returning true as it's a single-digit number.
The number is the maximum integer value (e.g., 2^31 - 1)	Reversing a large number like the max integer value can cause an integer overflow, which must be prevented by using a 64-bit integer for the reversed number or by reversing only half the number.
A number with an even number of digits (e.g., 1221)	The half-reversal approach works correctly by comparing the first half with the reversed second half when both halves are equal.
A number with an odd number of digits (e.g., 12321)	The half-reversal approach handles this by comparing the first half with the reversed second half after removing the middle digit.
The input is not a valid integer (e.g., null, undefined, string)	Depending on language and constraints, the solution might throw a type error or require explicit type checking at the beginning.

Negative numbers (e.g., -121)

How to Handle:

Negative numbers are never palindromes because the negative sign breaks the symmetry, so the function should return false immediately.

Single-digit numbers (0-9)

How to Handle:

Single-digit numbers are always palindromes, and the algorithm correctly handles this by reversing the number to itself.

Numbers ending in zero (e.g., 10, 120)

How to Handle:

If a positive number ends in zero, it cannot be a palindrome (except for 0 itself), so we can return false early.

The number is exactly zero

How to Handle:

Zero is a palindrome, and the logic correctly handles this by returning true as it's a single-digit number.

The number is the maximum integer value (e.g., 2^31 - 1)

How to Handle:

Reversing a large number like the max integer value can cause an integer overflow, which must be prevented by using a 64-bit integer for the reversed number or by reversing only half the number.

A number with an even number of digits (e.g., 1221)

How to Handle:

The half-reversal approach works correctly by comparing the first half with the reversed second half when both halves are equal.

A number with an odd number of digits (e.g., 12321)

How to Handle:

The half-reversal approach handles this by comparing the first half with the reversed second half after removing the middle digit.

The input is not a valid integer (e.g., null, undefined, string)

How to Handle:

Depending on language and constraints, the solution might throw a type error or require explicit type checking at the beginning.

0/0 Microsoft questions completed

0/0 completed