Jobs

Interviews

Discussions

Palindrome Number

Easy

Bloomberg LP

1 view

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.

Constraints:

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

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

Palindrome Number

Easy

Bloomberg LP

1 view

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.

Constraints:

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

Follow up: 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:

What is the range of possible values for the input integer x? Should I be concerned about integer overflow?
Can the input integer x be negative?
Should I treat a zero as a palindrome (i.e., should I return true if x is 0)?
Are there any specific performance constraints I should consider, assuming I am aiming for optimal time complexity?
Are we concerned about the space complexity of my solution?

Brute Force Solution

Approach

The brute force strategy for checking if a number is a palindrome involves directly comparing the original number to its reversed version. We create the reversed version, and then check if they are identical. If they are, the number is a palindrome.

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

Take the number you want to check.
Create a new number that is the reverse of the original number.
Compare the original number to the reversed number.
If the original number and the reversed number are exactly the same, then the original number is a palindrome.
If they are different, the original number is not a palindrome.

Code Implementation

def is_palindrome_brute_force(number_to_check):
    string_representation = str(number_to_check)

    reversed_string = string_representation[::-1]

    # Compare the original and reversed strings to check
    # if the number is a palindrome.

    if string_representation == reversed_string:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The time complexity is determined by the reversal of the input number, which has 'n' digits. Reversing the number requires iterating through each of the 'n' digits once. Comparing the reversed number with the original number also requires at most 'n' comparisons. Therefore, the overall time complexity is directly proportional to the number of digits in the input number, resulting in O(n).

Space Complexity

O(N) – The provided algorithm creates a reversed version of the input number. The reversed number requires storage proportional to the number of digits in the original number. If we denote the number of digits in the input number as N, then creating the reversed number requires O(N) space. Therefore, the space complexity is O(N).

Optimal Solution

Approach

Determining if a number is a palindrome can be done cleverly without reversing the entire number. The trick is to compare only half of the number to its reversed counterpart.

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

First, quickly check for some easy 'not palindrome' cases: negative numbers and numbers ending in zero (except zero itself).
If the initial checks pass, reverse only the second half of the number.
Then, compare the first half of the original number to the reversed second half.
If they match, the original number is a palindrome. If the original number has an odd number of digits, you also need to allow for the middle digit to be ignored during the comparison.

Code Implementation

def is_palindrome(number_to_check):
    # Handle negative numbers and numbers ending in 0
    if number_to_check < 0 or (number_to_check % 10 == 0 and number_to_check != 0):
        return False

    reversed_second_half = 0
    while number_to_check > reversed_second_half:
        reversed_second_half = (reversed_second_half * 10) + (number_to_check % 10)
        number_to_check //= 10

        # Compare first half to reversed second half

    # For odd length palindromes, account for middle digit
    if number_to_check == reversed_second_half or number_to_check == reversed_second_half // 10:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(log n) – The algorithm's time complexity is driven by the number of digits in the input number, n. We iterate through roughly half of the digits to reverse the second half of the number. The number of digits in a number n is proportional to log(n) in base 10. Therefore, the time complexity is O(log n).

Space Complexity

O(1) – The algorithm reverses the second half of the number but does so using a constant number of integer variables to store the reversed portion and potentially the original number. Therefore, the space used is independent of the input number's size, N. The space remains constant regardless of how many digits are in the input. Hence, the space complexity is O(1).

Edge Cases

Case	How to Handle
Negative numbers	Negative numbers cannot be palindromes because of the leading minus sign; return false immediately.
Single-digit numbers	Single-digit numbers are always palindromes; return true immediately.
Numbers ending in zero (excluding zero itself)	If a number ends in zero and is not zero itself, the reversed number will not end in zero, so it's not a palindrome; return false immediately.
Integer overflow during reversal	Check if the reversed number exceeds Integer.MAX_VALUE / Integer.MIN_VALUE during the reversal process and return false if overflow is detected.
Zero	Zero is a palindrome; return true.
Large positive numbers	The solution should efficiently handle large numbers without causing performance issues or stack overflow using iterative rather than recursive approach.
Maximum Integer Value (Integer.MAX_VALUE)	The solution should correctly classify Integer.MAX_VALUE as a non-palindrome
Numbers very close to integer limits	The solution should correctly identify palindromes and non-palindromes that are close to Integer.MAX_VALUE or Integer.MIN_VALUE.

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:

What is the range of possible values for the input integer x? Should I be concerned about integer overflow?
Can the input integer x be negative?
Should I treat a zero as a palindrome (i.e., should I return true if x is 0)?
Are there any specific performance constraints I should consider, assuming I am aiming for optimal time complexity?
Are we concerned about the space complexity of my solution?

Brute Force Solution

Approach

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

Take the number you want to check.
Create a new number that is the reverse of the original number.
Compare the original number to the reversed number.
If the original number and the reversed number are exactly the same, then the original number is a palindrome.
If they are different, the original number is not a palindrome.

Code Implementation

def is_palindrome_brute_force(number_to_check):
    string_representation = str(number_to_check)

    reversed_string = string_representation[::-1]

    # Compare the original and reversed strings to check
    # if the number is a palindrome.

    if string_representation == reversed_string:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Determining if a number is a palindrome can be done cleverly without reversing the entire number. The trick is to compare only half of the number to its reversed counterpart.

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

First, quickly check for some easy 'not palindrome' cases: negative numbers and numbers ending in zero (except zero itself).
If the initial checks pass, reverse only the second half of the number.
Then, compare the first half of the original number to the reversed second half.
If they match, the original number is a palindrome. If the original number has an odd number of digits, you also need to allow for the middle digit to be ignored during the comparison.

Code Implementation

def is_palindrome(number_to_check):
    # Handle negative numbers and numbers ending in 0
    if number_to_check < 0 or (number_to_check % 10 == 0 and number_to_check != 0):
        return False

    reversed_second_half = 0
    while number_to_check > reversed_second_half:
        reversed_second_half = (reversed_second_half * 10) + (number_to_check % 10)
        number_to_check //= 10

        # Compare first half to reversed second half

    # For odd length palindromes, account for middle digit
    if number_to_check == reversed_second_half or number_to_check == reversed_second_half // 10:
        return True
    else:
        return False

Try it yourself on LeetCode

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; return false immediately.
Single-digit numbers	Single-digit numbers are always palindromes; return true immediately.
Numbers ending in zero (excluding zero itself)	If a number ends in zero and is not zero itself, the reversed number will not end in zero, so it's not a palindrome; return false immediately.
Integer overflow during reversal	Check if the reversed number exceeds Integer.MAX_VALUE / Integer.MIN_VALUE during the reversal process and return false if overflow is detected.
Zero	Zero is a palindrome; return true.
Large positive numbers	The solution should efficiently handle large numbers without causing performance issues or stack overflow using iterative rather than recursive approach.
Maximum Integer Value (Integer.MAX_VALUE)	The solution should correctly classify Integer.MAX_VALUE as a non-palindrome
Numbers very close to integer limits	The solution should correctly identify palindromes and non-palindromes that are close to Integer.MAX_VALUE or Integer.MIN_VALUE.