Jobs

Interviews

Discussions

Palindrome Number

Easy

Amazon

3 views

Topics:

Bit Manipulation

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.

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

Palindrome Number

Easy

Amazon

3 views

Topics:

Bit Manipulation

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.

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

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:

Can the integer x be negative?
Is zero considered a palindrome?
What is the range of possible values for the integer x?
Are there any limitations on the amount of extra space I can use?
Could you provide a few example inputs and expected outputs?

Brute Force Solution

Approach

The brute force approach to checking if a number is a palindrome involves directly comparing the number to its reversed version. We'll create the reversed version and then see if the two are identical. If they are, the number is a palindrome; if not, it isn't.

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

First, take the number you want to check.
Transform the number into a string of digits.
Create a new string that represents the number written backward.
Compare the original string with the reversed string to see if they are exactly the same.
If the original string and reversed string are identical, then the original number is a palindrome.
If they are different, then the original number is not a palindrome.

Code Implementation

def is_palindrome_number_brute_force(number):
    # Convert the number to a string for easy reversal.
    number_string = str(number)

    # Create the reversed version of the string
    reversed_string = number_string[::-1]

    # Comparing the original and reversed strings to determine palindromicity.
    if number_string == reversed_string:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n) – The provided solution involves converting the integer to a string, which takes O(log n) time (where n is the integer value, not the number of digits but closely related). Reversing the string involves iterating through each character of the string once. Comparing the original and reversed strings also requires iterating through each character of the string once. These string operations are driven by the number of digits in the original number, which we can denote as 'n'. Therefore, the reversal and comparison steps each take O(n) time. The total operations are dominated by the string operations which involve at most a constant number of passes over the n digits leading to O(n) time complexity.

Space Complexity

O(N) – The provided solution converts the input number to a string, which requires storing the digits in a string format. Let N be the number of digits in the input number. A reversed string of length N is also created. Thus, the algorithm uses auxiliary space proportional to the number of digits in the input number N, because it creates the original string and the reversed string.

Optimal Solution

Approach

To check if a number is a palindrome, we can avoid converting the number to a string and directly compare digits. We compare the first and last digits, then the second and second-to-last digits, and so on, moving inwards. If any pair doesn't match, it's not a palindrome.

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

First, handle the simple case: negative numbers are never palindromes.
Next, if the number ends in zero (but isn't zero itself), it also cannot be a palindrome because the reversed number will not end in zero (or start in zero in the non-reversed way of reading) .
The main idea is to compare the first half of the number with the reversed second half.
To do this, we reverse the second half of the number while simultaneously reducing the original number by removing the last digit at each step.
Continue reversing digits until the reversed number is greater than or equal to the remaining part of the original number.
If the number of digits is odd, the reversed number will be exactly one digit longer. We can divide the reversed number by 10 to account for this 'middle' digit.
Finally, check if the reversed number is equal to the original number, or if the reversed number divided by 10 is equal to the original number. If either is true, the number is a palindrome.

Code Implementation

def is_palindrome(number):
    if number < 0:
        return False

    # Numbers ending in 0 (except 0 itself) are not palindromes
    if number % 10 == 0 and number != 0:
        return False

    reversed_number = 0
    while number > reversed_number:
        reversed_number = reversed_number * 10 + number % 10
        number //= 10

    # For odd length palindromes, remove the middle digit
    if number == reversed_number or number == reversed_number // 10:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(log n) – The algorithm iterates through the digits of the input number x. The number of iterations is proportional to the number of digits in x. Since the number of digits in a number x is approximately log(x), where the base of the logarithm depends on the number system (base 10 for decimal), the time complexity is O(log n), where n represents the input number x. Each operation within the while loop takes constant time. The loop continues until the reversed number is greater than or equal to the remaining part of the original number effectively processing half the digits, this halving factor is dropped in Big O complexity so it remains O(log n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It introduces a single variable to store the reversed second half of the number. The size of this variable does not depend on the number of digits in the input number. Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Edge Cases

Case	How to Handle
Negative numbers	Negative numbers cannot be palindromes because of the leading minus sign, so return false.
Zero	Zero is a palindrome, so return true.
Single digit positive numbers	Single digit positive numbers are palindromes, so return true.
Large positive integers that could lead to integer overflow when reversed	Employ techniques like comparing the first half of the number to the reversed second half, avoiding full reversal to prevent overflow.
Integer close to the maximum integer value (INT_MAX)	Consider that reversing such numbers could lead to overflow and handle with similar approach as 'Large positive integers'.
Numbers ending in zero (e.g., 10, 100) except 0 itself	Numbers ending in zero are not palindromes unless they are zero, so return false.
Maximum integer value (INT_MAX)	Directly check if the reversed version of INT_MAX is equal to it, preventing any potential overflow during the calculation.
Numbers with many leading zeros (e.g. 000121000)	Leading zeros are not usually represented in integer types and should not impact the palindrome property of the integer itself, but be mindful of implicit string conversion in some implementations.

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:

Can the integer x be negative?
Is zero considered a palindrome?
What is the range of possible values for the integer x?
Are there any limitations on the amount of extra space I can use?
Could you provide a few example inputs and expected outputs?

Brute Force Solution

Approach

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

First, take the number you want to check.
Transform the number into a string of digits.
Create a new string that represents the number written backward.
Compare the original string with the reversed string to see if they are exactly the same.
If the original string and reversed string are identical, then the original number is a palindrome.
If they are different, then the original number is not a palindrome.

Code Implementation

def is_palindrome_number_brute_force(number):
    # Convert the number to a string for easy reversal.
    number_string = str(number)

    # Create the reversed version of the string
    reversed_string = number_string[::-1]

    # Comparing the original and reversed strings to determine palindromicity.
    if number_string == reversed_string:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, handle the simple case: negative numbers are never palindromes.
Next, if the number ends in zero (but isn't zero itself), it also cannot be a palindrome because the reversed number will not end in zero (or start in zero in the non-reversed way of reading) .
The main idea is to compare the first half of the number with the reversed second half.
To do this, we reverse the second half of the number while simultaneously reducing the original number by removing the last digit at each step.
Continue reversing digits until the reversed number is greater than or equal to the remaining part of the original number.
If the number of digits is odd, the reversed number will be exactly one digit longer. We can divide the reversed number by 10 to account for this 'middle' digit.
Finally, check if the reversed number is equal to the original number, or if the reversed number divided by 10 is equal to the original number. If either is true, the number is a palindrome.

Code Implementation

def is_palindrome(number):
    if number < 0:
        return False

    # Numbers ending in 0 (except 0 itself) are not palindromes
    if number % 10 == 0 and number != 0:
        return False

    reversed_number = 0
    while number > reversed_number:
        reversed_number = reversed_number * 10 + number % 10
        number //= 10

    # For odd length palindromes, remove the middle digit
    if number == reversed_number or number == reversed_number // 10:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Negative numbers	Negative numbers cannot be palindromes because of the leading minus sign, so return false.
Zero	Zero is a palindrome, so return true.
Single digit positive numbers	Single digit positive numbers are palindromes, so return true.
Large positive integers that could lead to integer overflow when reversed	Employ techniques like comparing the first half of the number to the reversed second half, avoiding full reversal to prevent overflow.
Integer close to the maximum integer value (INT_MAX)	Consider that reversing such numbers could lead to overflow and handle with similar approach as 'Large positive integers'.
Numbers ending in zero (e.g., 10, 100) except 0 itself	Numbers ending in zero are not palindromes unless they are zero, so return false.
Maximum integer value (INT_MAX)	Directly check if the reversed version of INT_MAX is equal to it, preventing any potential overflow during the calculation.
Numbers with many leading zeros (e.g. 000121000)	Leading zeros are not usually represented in integer types and should not impact the palindrome property of the integer itself, but be mindful of implicit string conversion in some implementations.