Jobs

Interviews

Discussions

Strictly Palindromic Number

Medium

Asked by:

9 views

An integer n is strictly palindromic if, for every base b between 2 and n - 2 (inclusive), the string representation of the integer n in base b is palindromic.

Given an integer n, return true if n is strictly palindromic and false otherwise.

A string is palindromic if it reads the same forward and backward.

Example 1:

Input: n = 9
Output: false
Explanation: In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.

Example 2:

Input: n = 4
Output: false
Explanation: We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.

Constraints:

4 <= n <= 10⁵

Try coding it in LeetCode

Strictly Palindromic Number

Medium

Asked by:

9 views

An integer n is strictly palindromic if, for every base b between 2 and n - 2 (inclusive), the string representation of the integer n in base b is palindromic.

Given an integer n, return true if n is strictly palindromic and false otherwise.

A string is palindromic if it reads the same forward and backward.

Example 1:

Input: n = 9
Output: false
Explanation: In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.

Example 2:

Input: n = 4
Output: false
Explanation: We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.

Constraints:

4 <= n <= 10⁵

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 range of values for the input number 'n'? Can it be zero or negative?
In what base(s) should the number 'n' be non-palindromic to return true, or should it be non-palindromic in *all* bases between 2 and n-2 inclusive?
How should the function behave if n is less than 4, since bases between 2 and n-2 are not valid for such numbers?
Should I return 'true' or 'false' if the number is strictly palindromic, or strictly non-palindromic?
Are there any specific memory constraints I should consider, given that I will be converting the number to different bases?

Brute Force Solution

Approach

The brute force method for this problem involves checking every possible number base to see if the given number is a palindrome in that base. It's like trying out every possible number system to see if the number reads the same forwards and backwards. We start from base 2 and go up to the number itself minus 2.

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

Start with number base 2.
Convert the given number into the current number base.
Check if the converted number is a palindrome (reads the same backward as forward).
If it's NOT a palindrome, move to the next number base.
Repeat steps 2-4 for all number bases from 2 up to the original number minus 2.
If any of the converted numbers in these bases are NOT a palindrome, then the answer is 'no'.
If all of the converted numbers are palindromes, then the answer is 'yes'.

Code Implementation

def is_strictly_palindromic(number):
    # Iterate through all bases from 2 to n - 2.
    for number_base in range(2, number - 1):
        # Convert the number to the current base.
        converted_number = convert_to_base(number, number_base)

        # Check if the converted number is not a palindrome.
        if not is_palindrome(converted_number):

            # If not a palindrome, it's not strictly palindromic.
            return False

    return True

def convert_to_base(number, base):
    if number == 0:
        return [0]

    digits = []
    while number:
        digits.append(int(number % base))
        number //= base
    return digits[::-1]

def is_palindrome(digits):
    left = 0
    right = len(digits) - 1

    # Compare digits from the start and end.
    while left < right:
        if digits[left] != digits[right]:
            return False
        left += 1
        right -= 1

    return True

Big(O) Analysis

Time Complexity

O(n log² n) – The outer loop iterates from base 2 up to n-2, where n is the input number. Inside the loop, we convert the number to the current base, which takes O(log_b n) time, where b is the base. Since b varies from 2 to n-2, and the maximum base is n-2, this conversion roughly takes O(log n) time. The palindrome check on the converted number, which has at most log_2 n digits, takes O(log n) time. Therefore, the conversion and palindrome check inside the loop takes O(log n) + O(log n) which simplifies to O(log n). The outer loop runs n-3 times, but we can simplify this to n. Since each conversion to a different base takes O(log n) time, and the palindrome check takes O(log n) time, the total time complexity becomes O(n * log n * log n), which is O(n log² n).

Space Complexity

O(log N) – The algorithm converts the input number N to different bases. The converted number is stored as a string or a list of digits. The maximum number of digits required to represent N in any base between 2 and N-2 is O(log N), specifically the logarithm base 2. The auxiliary space used to store the converted number therefore grows logarithmically with the input N. Thus, the space complexity is O(log N).

Optimal Solution

Approach

A number is strictly palindromic if it's a palindrome when represented in every base from 2 to the number minus 2. The key insight is realizing that almost no number can possibly meet this condition. We use this understanding to avoid unnecessary calculations and quickly determine the answer.

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

Realize that any number greater than 3 can be represented in base 'number minus 1' as '11'.
Since '11' is always a palindrome, that base is no help.
Consider the number represented in base 2, and also base (number - 2).
If we can prove that it is not a palindrome in at least one base then we can return that it is not strictly palindromic without doing any other checks.
Consider expressing the original number 'n' in base 'n-2'.
In base 'n-2', the number 'n' is represented as '12' because (1 * (n-2)^1) + (2 * (n-2)^0) = n - 2 + 2 = n.
The number '12' is never a palindrome, so the number 'n' is never strictly palindromic, unless n is <= 3. Because the original problem states that the input number will be greater than 3.
Therefore, any number greater than 3 will never be strictly palindromic, so we can automatically return false.

Code Implementation

def is_strictly_palindromic(number) -> bool:
    # Numbers <= 3 cannot meet the input constraint.
    if number <= 3:
        return False

    # Numbers > 3 are not strictly palindromic.
    # This is based on the fact that any number > 3 will be 12 in base n-2. 
    return False

Big(O) Analysis

Time Complexity

O(1) – The solution directly returns 'false' for any number greater than 3. This involves a single comparison (n > 3) and a return statement. There are no loops or recursive calls involved, and the execution time does not depend on the input number 'n'. Therefore, the time complexity is constant.

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it does not use any auxiliary data structures that scale with the input number 'n'. It relies solely on the constant values inherent in the problem analysis and returns 'false' immediately for numbers greater than 3, without performing any calculations or storing any intermediate results dependent on the input 'n'. Therefore, the space used remains constant regardless of the input size.

Edge Cases

Case	How to Handle
Input is a negative number	Return false because negative numbers cannot be strictly palindromic across bases.
Input is 0 or 1	Return false since the base-n representation for n > number will always be the number itself, which isn't palindromic by the definition given in the problem.
Integer overflow during base conversion for large inputs	Check if the base conversion result exceeds the maximum allowed integer value and return false if it does, effectively limiting the tested bases or input number to prevent overflow.
Input is a prime number	Prime numbers will likely require a base close to the number itself to potentially form a palindrome, requiring efficient base conversion.
Input is a power of 2 (e.g., 8, 16, 32)	Powers of 2 might have simple binary representations, but it is still unlikely that they will be palindromic in ALL bases from 2 to n-2.
Large input number, leading to significant computation time during base conversions	Optimize base conversion to be as efficient as possible (e.g., using bitwise operations where feasible) and consider early termination if a non-palindromic base is found.
Number is close to the maximum integer value	Handle integer overflows carefully when calculating remainders or quotients during base conversion to avoid incorrect results.
Input number is already a palindrome in base 10	The solution must still perform the base conversions and palindrome checks for bases 2 through n-2, even if the number is a palindrome in base 10.

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 values for the input number 'n'? Can it be zero or negative?
In what base(s) should the number 'n' be non-palindromic to return true, or should it be non-palindromic in *all* bases between 2 and n-2 inclusive?
How should the function behave if n is less than 4, since bases between 2 and n-2 are not valid for such numbers?
Should I return 'true' or 'false' if the number is strictly palindromic, or strictly non-palindromic?
Are there any specific memory constraints I should consider, given that I will be converting the number to different bases?

Brute Force Solution

Approach

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

Start with number base 2.
Convert the given number into the current number base.
Check if the converted number is a palindrome (reads the same backward as forward).
If it's NOT a palindrome, move to the next number base.
Repeat steps 2-4 for all number bases from 2 up to the original number minus 2.
If any of the converted numbers in these bases are NOT a palindrome, then the answer is 'no'.
If all of the converted numbers are palindromes, then the answer is 'yes'.

Code Implementation

def is_strictly_palindromic(number):
    # Iterate through all bases from 2 to n - 2.
    for number_base in range(2, number - 1):
        # Convert the number to the current base.
        converted_number = convert_to_base(number, number_base)

        # Check if the converted number is not a palindrome.
        if not is_palindrome(converted_number):

            # If not a palindrome, it's not strictly palindromic.
            return False

    return True

def convert_to_base(number, base):
    if number == 0:
        return [0]

    digits = []
    while number:
        digits.append(int(number % base))
        number //= base
    return digits[::-1]

def is_palindrome(digits):
    left = 0
    right = len(digits) - 1

    # Compare digits from the start and end.
    while left < right:
        if digits[left] != digits[right]:
            return False
        left += 1
        right -= 1

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Realize that any number greater than 3 can be represented in base 'number minus 1' as '11'.
Since '11' is always a palindrome, that base is no help.
Consider the number represented in base 2, and also base (number - 2).
If we can prove that it is not a palindrome in at least one base then we can return that it is not strictly palindromic without doing any other checks.
Consider expressing the original number 'n' in base 'n-2'.
In base 'n-2', the number 'n' is represented as '12' because (1 * (n-2)^1) + (2 * (n-2)^0) = n - 2 + 2 = n.
The number '12' is never a palindrome, so the number 'n' is never strictly palindromic, unless n is <= 3. Because the original problem states that the input number will be greater than 3.
Therefore, any number greater than 3 will never be strictly palindromic, so we can automatically return false.

Code Implementation

def is_strictly_palindromic(number) -> bool:
    # Numbers <= 3 cannot meet the input constraint.
    if number <= 3:
        return False

    # Numbers > 3 are not strictly palindromic.
    # This is based on the fact that any number > 3 will be 12 in base n-2. 
    return False

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is a negative number	Return false because negative numbers cannot be strictly palindromic across bases.
Input is 0 or 1	Return false since the base-n representation for n > number will always be the number itself, which isn't palindromic by the definition given in the problem.
Integer overflow during base conversion for large inputs	Check if the base conversion result exceeds the maximum allowed integer value and return false if it does, effectively limiting the tested bases or input number to prevent overflow.
Input is a prime number	Prime numbers will likely require a base close to the number itself to potentially form a palindrome, requiring efficient base conversion.
Input is a power of 2 (e.g., 8, 16, 32)	Powers of 2 might have simple binary representations, but it is still unlikely that they will be palindromic in ALL bases from 2 to n-2.
Large input number, leading to significant computation time during base conversions	Optimize base conversion to be as efficient as possible (e.g., using bitwise operations where feasible) and consider early termination if a non-palindromic base is found.
Number is close to the maximum integer value	Handle integer overflows carefully when calculating remainders or quotients during base conversion to avoid incorrect results.
Input number is already a palindrome in base 10	The solution must still perform the base conversions and palindrome checks for bases 2 through n-2, even if the number is a palindrome in base 10.