Jobs

Interviews

Discussions

Super Palindromes

#935 Most AskedHard

Super Palindromes #935 Most Asked

Hard

Microsoft

9 views

Topics:

StringsTwo Pointers

Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.

Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].

Example 1:

Input: left = "4", right = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

Example 2:

Input: left = "1", right = "2"
Output: 1

Constraints:

1 <= left.length, right.length <= 18
left and right consist of only digits.
left and right cannot have leading zeros.
left and right represent integers in the range [1, 10¹⁸ - 1].
left is less than or equal to right.

Try coding it in LeetCode

Super Palindromes

#935 Most AskedHard

Super Palindromes #935 Most Asked

Hard

Microsoft

9 views

Topics:

StringsTwo Pointers

Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.

Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].

Example 1:

Input: left = "4", right = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

Example 2:

Input: left = "1", right = "2"
Output: 1

Constraints:

1 <= left.length, right.length <= 18
left and right consist of only digits.
left and right cannot have leading zeros.
left and right represent integers in the range [1, 10¹⁸ - 1].
left is less than or equal to right.

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:

What is the upper bound for the input number n? Should I be concerned about integer overflow?
Are we only considering positive integers, or can n be zero or negative?
By 'superpalindrome,' do you mean that both the number and its square must be palindromes when represented in base 10?
If no superpalindromes exist within the given range, what should I return?
Is there a particular performance target, such as a maximum allowed runtime for very large input values of n?

Brute Force Solution

Approach

The brute force strategy for super palindromes involves checking every number within the given range to see if it meets the criteria. We'll go through each number, determine if it's a palindrome, and if its square is also a palindrome.

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

Consider each number one by one within the given range.
For each number, first check if the number itself is a palindrome. A palindrome reads the same forwards and backward.
If the number is a palindrome, then calculate its square.
Next, check if the square of that number is also a palindrome.
If both the number and its square are palindromes, then we count it as a super palindrome.
Repeat this process for every number within the given range and keep track of the count of super palindromes.

Code Implementation

def is_super_palindrome(left_bound, right_bound):
    super_palindrome_count = 0

    for number in range(int(left_bound**0.5), int(right_bound**0.5) + 1):
        # Checking every number within sqrt(left_bound) and sqrt(right_bound)
        number_string = str(number)

        if number_string == number_string[::-1]:
            # Proceed only if the number is a palindrome

            square = number * number
            square_string = str(square)

            if square_string == square_string[::-1]:
                # Proceed only if the number's square is a palindrome
                if square >= int(left_bound) and square <= int(right_bound):
                    # Verify that the square is within the specified bounds
                    super_palindrome_count += 1

    return super_palindrome_count

Big(O) Analysis

Time Complexity

O(r^(3/2)) – Let r be the upper bound of the range (right - left). The algorithm iterates through each number x within the range [sqrt(left), sqrt(right)], which is approximately O(sqrt(r)). For each number x, it checks if x is a palindrome which takes O(log x) time. It then calculates x*x and checks if x*x is a palindrome which takes O(log x*x) = O(2 log x) = O(log x) time. Since log x will always be smaller than sqrt(x), we can say that for each x the palindrome checks are O(sqrt(x)). Therefore the total complexity is roughly sqrt(r) * O(sqrt(x)). Since x <= sqrt(r), then O(sqrt(x)) <= O(r^(1/4)). This results in O(sqrt(r) * log(sqrt(r))) which simplifies to O(r^(1/2) * r^(1/4)). This simplifies further to O(r^(3/4)). Since calculating the square of each element x <= sqrt(right) takes O(1) which is negligable compared to palindrome checks which are logarithmic in size, the simplified Big O time complexity becomes O(r^(3/4)).

Space Complexity

O(1) – The brute force approach, as described, iterates through numbers within a given range, checking if a number and its square are palindromes. It does not use any auxiliary data structures that scale with the input range. Temporary variables are used for calculations (like storing the square of a number) and palindrome checks, but these are constant in size regardless of the input size. Therefore, the space complexity is constant.

Optimal Solution

Approach

To find super palindromes efficiently, we avoid checking every number. We cleverly generate palindromes and their squares, then check if the square is also a palindrome, making the search much faster.

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

First, recognize that super palindromes are squares of palindromes, and generating palindrome roots is easier than generating super palindromes directly.
Create a function to generate palindrome numbers. You can do this by starting with single-digit numbers and building outwards, mirroring digits to create palindromes.
Generate palindromes of a reasonable size. Since the super palindrome must fall within a given range, calculate the maximum possible palindrome root needed, by square rooting the upper limit of the range.
For each palindrome root you generate, square it.
Check if the square is within the given range. If not, skip it.
Check if the square is a palindrome. If so, you've found a super palindrome.
Keep track of the super palindromes you find, making sure to avoid duplicates.
Continue this process until you've generated all relevant palindrome roots and their squares. The number of super palindromes found is the answer.

Code Implementation

def superpalindromes_in_range(left_string, right_string):
    left = int(left_string)
    right = int(right_string)
    count = 0
    maximum_palindrome_root =       int(right**0.5) + 1

    def is_palindrome(number):
        number_string = str(number)
        return number_string == number_string[::-1]

    def generate_palindromes(length):
        palindromes = []
        # Ensures numbers 1-9 are generated before proceeding.
        if length == 1:
            for digit in range(1, 10):
                palindromes.append(digit)
            return palindromes

        for i in range(10**(length // 2 - (length % 2 == 0)), 10**(length // 2)):
            string_representation = str(i)
            if length % 2 == 0:
                palindrome = int(string_representation + string_representation[::-1])
            else:
                for middle_digit in range(10):
                    palindrome = int(string_representation + str(middle_digit) + string_representation[::-1])
                    if palindrome < maximum_palindrome_root:
                        palindromes.append(palindrome)
            if length % 2 == 0 and palindrome < maximum_palindrome_root:
              palindromes.append(int(string_representation + string_representation[::-1]))
        return palindromes

    generated_palindromes = []
    for length in range(1, 6):
        generated_palindromes.extend(generate_palindromes(length))

    for palindrome_root in generated_palindromes:
        square = palindrome_root**2

        # Avoid unnecessary calculations if the square is out of range.
        if square >= left and square <= right:

            # Only increment the count if the square is also a palindrome.
            if is_palindrome(square):
                count += 1

    return count

Big(O) Analysis

Time Complexity

O(sqrt(n)) – The dominant factor in the time complexity is generating palindromes up to the square root of the upper bound 'n' of the range. Generating each palindrome takes time proportional to the number of digits it has. The number of palindromes generated is roughly proportional to the square root of n since we only need to generate palindromes whose squares are within the range [lower bound, upper bound]. Squaring the generated palindrome and checking if the square is a palindrome takes O(log n) time, but this is dominated by the number of palindromes generated. Therefore, the overall time complexity is approximately O(sqrt(n)).

Space Complexity

O(sqrt(N)) – The algorithm generates palindrome roots up to the square root of the upper bound of the input range (N). These palindrome roots, although generated iteratively, are not stored in a data structure that grows proportionally to sqrt(N). However, we also create a set (or similar data structure) to store the super palindromes found to avoid duplicates. In the worst-case scenario, the number of super palindromes can grow proportionally to the square root of N, leading to a set size of O(sqrt(N)). This set dominates the auxiliary space used. Other variables like individual palindrome numbers and their squares use constant space and do not impact the overall space complexity.

Edge Cases

Case	How to Handle
Empty range (L > R)	Return an empty list if the input range is invalid (L > R).
Single-digit range (L and R are single digits)	Manually check if 1, 4, and 9 are within the range and add them since their square roots are single digits.
Large range causing potential integer overflow when squaring palindromes	Use long data type to avoid integer overflow when calculating the square of palindromes, and limit search space accordingly.
Maximum value of R is close to the square of largest possible palindrome that fits within the allowed range	Carefully consider the range for generating palindromes to ensure the squares do not exceed R.
Input range contains only non-super palindromes	Return an empty list if no super palindromes are found within the specified range.
Palindromes with leading zeros are invalid	Avoid generating palindromes with leading zeros during the palindrome generation process.
Range includes 0, which would cause issues if treated as a potential square	Treat zero as a special case and check if it's included in the range before beginning the main search.
Input range with L=1 and R=very large number, requiring efficient palindrome generation	Optimize the palindrome generation algorithm to avoid generating unnecessary or duplicate palindromes.

Empty range (L > R)

How to Handle:

Return an empty list if the input range is invalid (L > R).

Single-digit range (L and R are single digits)

How to Handle:

Manually check if 1, 4, and 9 are within the range and add them since their square roots are single digits.

Large range causing potential integer overflow when squaring palindromes

How to Handle:

Use long data type to avoid integer overflow when calculating the square of palindromes, and limit search space accordingly.

Maximum value of R is close to the square of largest possible palindrome that fits within the allowed range

How to Handle:

Carefully consider the range for generating palindromes to ensure the squares do not exceed R.

Input range contains only non-super palindromes

How to Handle:

Return an empty list if no super palindromes are found within the specified range.

Palindromes with leading zeros are invalid

How to Handle:

Avoid generating palindromes with leading zeros during the palindrome generation process.

Range includes 0, which would cause issues if treated as a potential square

How to Handle:

Treat zero as a special case and check if it's included in the range before beginning the main search.

Input range with L=1 and R=very large number, requiring efficient palindrome generation

How to Handle:

Optimize the palindrome generation algorithm to avoid generating unnecessary or duplicate palindromes.

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 upper bound for the input number n? Should I be concerned about integer overflow?
Are we only considering positive integers, or can n be zero or negative?
By 'superpalindrome,' do you mean that both the number and its square must be palindromes when represented in base 10?
If no superpalindromes exist within the given range, what should I return?
Is there a particular performance target, such as a maximum allowed runtime for very large input values of n?

Brute Force Solution

Approach

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

Consider each number one by one within the given range.
For each number, first check if the number itself is a palindrome. A palindrome reads the same forwards and backward.
If the number is a palindrome, then calculate its square.
Next, check if the square of that number is also a palindrome.
If both the number and its square are palindromes, then we count it as a super palindrome.
Repeat this process for every number within the given range and keep track of the count of super palindromes.

Code Implementation

def is_super_palindrome(left_bound, right_bound):
    super_palindrome_count = 0

    for number in range(int(left_bound**0.5), int(right_bound**0.5) + 1):
        # Checking every number within sqrt(left_bound) and sqrt(right_bound)
        number_string = str(number)

        if number_string == number_string[::-1]:
            # Proceed only if the number is a palindrome

            square = number * number
            square_string = str(square)

            if square_string == square_string[::-1]:
                # Proceed only if the number's square is a palindrome
                if square >= int(left_bound) and square <= int(right_bound):
                    # Verify that the square is within the specified bounds
                    super_palindrome_count += 1

    return super_palindrome_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, recognize that super palindromes are squares of palindromes, and generating palindrome roots is easier than generating super palindromes directly.
Create a function to generate palindrome numbers. You can do this by starting with single-digit numbers and building outwards, mirroring digits to create palindromes.
Generate palindromes of a reasonable size. Since the super palindrome must fall within a given range, calculate the maximum possible palindrome root needed, by square rooting the upper limit of the range.
For each palindrome root you generate, square it.
Check if the square is within the given range. If not, skip it.
Check if the square is a palindrome. If so, you've found a super palindrome.
Keep track of the super palindromes you find, making sure to avoid duplicates.
Continue this process until you've generated all relevant palindrome roots and their squares. The number of super palindromes found is the answer.

Code Implementation

def superpalindromes_in_range(left_string, right_string):
    left = int(left_string)
    right = int(right_string)
    count = 0
    maximum_palindrome_root =       int(right**0.5) + 1

    def is_palindrome(number):
        number_string = str(number)
        return number_string == number_string[::-1]

    def generate_palindromes(length):
        palindromes = []
        # Ensures numbers 1-9 are generated before proceeding.
        if length == 1:
            for digit in range(1, 10):
                palindromes.append(digit)
            return palindromes

        for i in range(10**(length // 2 - (length % 2 == 0)), 10**(length // 2)):
            string_representation = str(i)
            if length % 2 == 0:
                palindrome = int(string_representation + string_representation[::-1])
            else:
                for middle_digit in range(10):
                    palindrome = int(string_representation + str(middle_digit) + string_representation[::-1])
                    if palindrome < maximum_palindrome_root:
                        palindromes.append(palindrome)
            if length % 2 == 0 and palindrome < maximum_palindrome_root:
              palindromes.append(int(string_representation + string_representation[::-1]))
        return palindromes

    generated_palindromes = []
    for length in range(1, 6):
        generated_palindromes.extend(generate_palindromes(length))

    for palindrome_root in generated_palindromes:
        square = palindrome_root**2

        # Avoid unnecessary calculations if the square is out of range.
        if square >= left and square <= right:

            # Only increment the count if the square is also a palindrome.
            if is_palindrome(square):
                count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty range (L > R)	Return an empty list if the input range is invalid (L > R).
Single-digit range (L and R are single digits)	Manually check if 1, 4, and 9 are within the range and add them since their square roots are single digits.
Large range causing potential integer overflow when squaring palindromes	Use long data type to avoid integer overflow when calculating the square of palindromes, and limit search space accordingly.
Maximum value of R is close to the square of largest possible palindrome that fits within the allowed range	Carefully consider the range for generating palindromes to ensure the squares do not exceed R.
Input range contains only non-super palindromes	Return an empty list if no super palindromes are found within the specified range.
Palindromes with leading zeros are invalid	Avoid generating palindromes with leading zeros during the palindrome generation process.
Range includes 0, which would cause issues if treated as a potential square	Treat zero as a special case and check if it's included in the range before beginning the main search.
Input range with L=1 and R=very large number, requiring efficient palindrome generation	Optimize the palindrome generation algorithm to avoid generating unnecessary or duplicate palindromes.

Empty range (L > R)

How to Handle:

Return an empty list if the input range is invalid (L > R).

Single-digit range (L and R are single digits)

How to Handle:

Manually check if 1, 4, and 9 are within the range and add them since their square roots are single digits.

Large range causing potential integer overflow when squaring palindromes

How to Handle:

Use long data type to avoid integer overflow when calculating the square of palindromes, and limit search space accordingly.

Maximum value of R is close to the square of largest possible palindrome that fits within the allowed range

How to Handle:

Carefully consider the range for generating palindromes to ensure the squares do not exceed R.

Input range contains only non-super palindromes

How to Handle:

Return an empty list if no super palindromes are found within the specified range.

Palindromes with leading zeros are invalid

How to Handle:

Avoid generating palindromes with leading zeros during the palindrome generation process.

Range includes 0, which would cause issues if treated as a potential square

How to Handle:

Treat zero as a special case and check if it's included in the range before beginning the main search.

Input range with L=1 and R=very large number, requiring efficient palindrome generation

How to Handle:

Optimize the palindrome generation algorithm to avoid generating unnecessary or duplicate palindromes.

0/1114 Microsoft questions completed

0/1114 completed