Jobs

Interviews

Discussions

Find the Largest Palindrome Divisible by K

Hard

Asked by:

11 views

Topics:

StringsTwo Pointers

You are given two positive integers n and k.

An integer x is called k-palindromic if:

x is a palindrome.
x is divisible by k.

Return the largest integer having n digits (as a string) that is k-palindromic.

Note that the integer must not have leading zeros.

Example 1:

Input: n = 3, k = 5

Output: "595"

Explanation:

595 is the largest k-palindromic integer with 3 digits.

Example 2:

Input: n = 1, k = 4

Output: "8"

Explanation:

4 and 8 are the only k-palindromic integers with 1 digit.

Example 3:

Input: n = 5, k = 6

Output: "89898"

Constraints:

1 <= n <= 10⁵
1 <= k <= 9

Try coding it in LeetCode

Find the Largest Palindrome Divisible by K

Hard

Asked by:

11 views

Topics:

StringsTwo Pointers

You are given two positive integers n and k.

An integer x is called k-palindromic if:

x is a palindrome.
x is divisible by k.

Return the largest integer having n digits (as a string) that is k-palindromic.

Note that the integer must not have leading zeros.

Example 1:

Input: n = 3, k = 5

Output: "595"

Explanation:

595 is the largest k-palindromic integer with 3 digits.

Example 2:

Input: n = 1, k = 4

Output: "8"

Explanation:

4 and 8 are the only k-palindromic integers with 1 digit.

Example 3:

Input: n = 5, k = 6

Output: "89898"

Constraints:

1 <= n <= 10⁵
1 <= k <= 9

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 maximum possible value of K, and what data type should I use to store the palindrome (e.g., int, long)?
If no palindrome exists that is divisible by K, what value should I return?
Is K guaranteed to be greater than 0?
Are we looking for palindromes in the decimal representation of numbers, or some other base?
By 'divisible by K', do you mean with no remainder (i.e., a true mathematical divisibility)?
Should I consider only positive palindromes?

Brute Force Solution

Approach

We need to find the biggest palindrome number that can be divided exactly by another number. The brute force way is to check every possible palindrome, from largest to smallest, until we find one that works.

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

Start with the largest possible palindrome number (a number that reads the same forwards and backward).
Check if this number can be divided exactly by the given number, without any remainder.
If it can, then we have found our answer and we are done.
If not, then reduce the number slightly to make a new palindrome, always making sure we are creating palindromes.
Repeat steps 2-4, checking smaller and smaller palindromes, until we find one that is divisible by the given number.
Once we find such a palindrome, we know that this is the largest one because we started our search from the largest possible value.

Code Implementation

def find_largest_palindrome_divisible_by_k(divisor):
    largest_number = 999
    # Start from the largest 3-digit number
    for number in range(largest_number, 99, -1):
        number_string = str(number)
        palindrome = int(number_string + number_string[::-1])

        #Check divisibility condition
        if palindrome % divisor == 0:

            return palindrome

    return -1

Big(O) Analysis

Time Complexity

O(10^(n/2)) – Let n be the number of digits in the desired palindrome. The outer loop iterates through potential palindromes, starting from the largest possible n-digit palindrome and decreasing. The number of n-digit palindromes is approximately 10^(n/2) since we only need to iterate through the first half of the digits. Inside the loop, we perform a division operation. Therefore, the time complexity is dominated by the number of palindromes we potentially check, leading to O(10^(n/2)). The division operation within the loop takes a negligible amount of time in comparison to generating and checking each palindrome.

Space Complexity

O(1) – The provided algorithm iterates through palindrome numbers and checks for divisibility. It does not explicitly mention creating any auxiliary data structures like arrays, lists, or hash maps. The algorithm likely uses a few integer variables to store the current palindrome being tested and the result of the divisibility check. Since the number of integer variables is constant regardless of the input 'K' (the divisor), the space complexity is O(1).

Optimal Solution

Approach

The goal is to find the largest palindrome (a number that reads the same forwards and backward) that is also divisible by a given number. The key idea is to generate palindromes in decreasing order of magnitude and check for divisibility, avoiding unnecessary checks on smaller numbers.

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

Start by constructing the largest possible palindrome with a certain number of digits.
Check if this largest palindrome is divisible by the given number.
If it is divisible, you've found your answer!
If not, create the next largest palindrome with the same number of digits.
Continue checking each successively smaller palindrome for divisibility until you find one that works or exhaust all possibilities for that number of digits.
If no palindrome is found with that digit count, move to the next smaller digit count and repeat the process.
This ensures you find the *largest* possible palindrome first, optimizing the search.

Code Implementation

def find_largest_palindrome_divisible_by_k(divisor):
    for number_of_digits in range(17, 0, -1):
        # Iterate from largest possible palindrome to smallest.
        if number_of_digits % 2 == 0:
            max_half = 10**(number_of_digits // 2) - 1
        else:
            max_half = 10**((number_of_digits - 1) // 2) - 1

        for half in range(max_half, -1, -1):
            half_string = str(half)
            if number_of_digits % 2 == 0:
                palindrome = int(half_string + half_string[::-1])
            else:
                palindrome = int(half_string + half_string[:-1][::-1])

            # Key step: Check if the palindrome is divisible by k.
            if palindrome % divisor == 0:

                return palindrome

    return None

Big(O) Analysis

Time Complexity

O(10^(n/2)) – Let n be the number of digits of the largest possible palindrome we need to check. The outer loop implicitly iterates through decreasing numbers of digits for the palindrome. For a given number of digits, the core of the algorithm involves generating palindromes starting from the largest possible and decreasing. Constructing palindromes with n digits requires generating the first half of the digits (n/2 digits). The divisibility check is a constant time operation. Since we check palindromes in decreasing order, the number of palindromes checked is bounded by the number of possible combinations for the first half of the digits, which is 10^(n/2). Therefore, the overall time complexity is O(10^(n/2)).

Space Complexity

O(1) – The algorithm primarily involves generating and checking palindromes. The generation process doesn't require storing a collection of palindromes; it creates them one at a time for divisibility checks. The algorithm stores individual palindrome numbers or parts of palindrome numbers for construction, as well as boolean variables for control flow and comparison. These individual variables occupy a constant amount of space, independent of any input parameter N (implicitly referring to the magnitude of the target palindrome). Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
K equals 0	Return -1 since division by zero is undefined and no palindrome can be divisible by it.
K equals 1	The largest palindrome is 9 repeated n times, where n is the number of digits required, so directly construct and return that palindrome.
Input consists of a single digit (e.g., finding the largest palindrome divisible by K within single-digit numbers)	Check if any single-digit number divisible by K is a palindrome; if so, return the largest; otherwise return -1.
Required number of digits is very large (e.g., 1000 digits), potentially leading to performance issues.	Use string manipulation and avoid unnecessary numeric conversions to optimize performance for large numbers of digits.
No palindrome exists for the required number of digits divisible by K (e.g., searching for a 2-digit palindrome divisible by 7 which doesn't exist larger than 9000).	Return -1 when the iteration reaches the smallest possible palindrome for the given number of digits.
Integer overflow during intermediate calculations (e.g., when calculating the product of digits or when constructing palindromes).	Use string-based palindrome construction and modular arithmetic when checking divisibility to prevent overflow.
K is a very large number	The search space can be reduced by first considering the largest possible palindrome for the given digits, and check its divisibility by K.
The solution fails to create the largest number after selecting the prefix.	Ensure that the palindrome is constructed correctly by mirroring the prefix in reverse order around the middle point of the number.

K equals 0

How to Handle:

Return -1 since division by zero is undefined and no palindrome can be divisible by it.

K equals 1

How to Handle:

The largest palindrome is 9 repeated n times, where n is the number of digits required, so directly construct and return that palindrome.

Input consists of a single digit (e.g., finding the largest palindrome divisible by K within single-digit numbers)

How to Handle:

Check if any single-digit number divisible by K is a palindrome; if so, return the largest; otherwise return -1.

Required number of digits is very large (e.g., 1000 digits), potentially leading to performance issues.

How to Handle:

Use string manipulation and avoid unnecessary numeric conversions to optimize performance for large numbers of digits.

No palindrome exists for the required number of digits divisible by K (e.g., searching for a 2-digit palindrome divisible by 7 which doesn't exist larger than 9000).

How to Handle:

Return -1 when the iteration reaches the smallest possible palindrome for the given number of digits.

Integer overflow during intermediate calculations (e.g., when calculating the product of digits or when constructing palindromes).

How to Handle:

Use string-based palindrome construction and modular arithmetic when checking divisibility to prevent overflow.

K is a very large number

How to Handle:

The search space can be reduced by first considering the largest possible palindrome for the given digits, and check its divisibility by K.

The solution fails to create the largest number after selecting the prefix.

How to Handle:

Ensure that the palindrome is constructed correctly by mirroring the prefix in reverse order around the middle point of the number.

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 maximum possible value of K, and what data type should I use to store the palindrome (e.g., int, long)?
If no palindrome exists that is divisible by K, what value should I return?
Is K guaranteed to be greater than 0?
Are we looking for palindromes in the decimal representation of numbers, or some other base?
By 'divisible by K', do you mean with no remainder (i.e., a true mathematical divisibility)?
Should I consider only positive palindromes?

Brute Force Solution

Approach

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

Start with the largest possible palindrome number (a number that reads the same forwards and backward).
Check if this number can be divided exactly by the given number, without any remainder.
If it can, then we have found our answer and we are done.
If not, then reduce the number slightly to make a new palindrome, always making sure we are creating palindromes.
Repeat steps 2-4, checking smaller and smaller palindromes, until we find one that is divisible by the given number.
Once we find such a palindrome, we know that this is the largest one because we started our search from the largest possible value.

Code Implementation

def find_largest_palindrome_divisible_by_k(divisor):
    largest_number = 999
    # Start from the largest 3-digit number
    for number in range(largest_number, 99, -1):
        number_string = str(number)
        palindrome = int(number_string + number_string[::-1])

        #Check divisibility condition
        if palindrome % divisor == 0:

            return palindrome

    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by constructing the largest possible palindrome with a certain number of digits.
Check if this largest palindrome is divisible by the given number.
If it is divisible, you've found your answer!
If not, create the next largest palindrome with the same number of digits.
Continue checking each successively smaller palindrome for divisibility until you find one that works or exhaust all possibilities for that number of digits.
If no palindrome is found with that digit count, move to the next smaller digit count and repeat the process.
This ensures you find the *largest* possible palindrome first, optimizing the search.

Code Implementation

def find_largest_palindrome_divisible_by_k(divisor):
    for number_of_digits in range(17, 0, -1):
        # Iterate from largest possible palindrome to smallest.
        if number_of_digits % 2 == 0:
            max_half = 10**(number_of_digits // 2) - 1
        else:
            max_half = 10**((number_of_digits - 1) // 2) - 1

        for half in range(max_half, -1, -1):
            half_string = str(half)
            if number_of_digits % 2 == 0:
                palindrome = int(half_string + half_string[::-1])
            else:
                palindrome = int(half_string + half_string[:-1][::-1])

            # Key step: Check if the palindrome is divisible by k.
            if palindrome % divisor == 0:

                return palindrome

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
K equals 0	Return -1 since division by zero is undefined and no palindrome can be divisible by it.
K equals 1	The largest palindrome is 9 repeated n times, where n is the number of digits required, so directly construct and return that palindrome.
Input consists of a single digit (e.g., finding the largest palindrome divisible by K within single-digit numbers)	Check if any single-digit number divisible by K is a palindrome; if so, return the largest; otherwise return -1.
Required number of digits is very large (e.g., 1000 digits), potentially leading to performance issues.	Use string manipulation and avoid unnecessary numeric conversions to optimize performance for large numbers of digits.
No palindrome exists for the required number of digits divisible by K (e.g., searching for a 2-digit palindrome divisible by 7 which doesn't exist larger than 9000).	Return -1 when the iteration reaches the smallest possible palindrome for the given number of digits.
Integer overflow during intermediate calculations (e.g., when calculating the product of digits or when constructing palindromes).	Use string-based palindrome construction and modular arithmetic when checking divisibility to prevent overflow.
K is a very large number	The search space can be reduced by first considering the largest possible palindrome for the given digits, and check its divisibility by K.
The solution fails to create the largest number after selecting the prefix.	Ensure that the palindrome is constructed correctly by mirroring the prefix in reverse order around the middle point of the number.

K equals 0

How to Handle:

Return -1 since division by zero is undefined and no palindrome can be divisible by it.

K equals 1

How to Handle:

The largest palindrome is 9 repeated n times, where n is the number of digits required, so directly construct and return that palindrome.

Input consists of a single digit (e.g., finding the largest palindrome divisible by K within single-digit numbers)

How to Handle:

Check if any single-digit number divisible by K is a palindrome; if so, return the largest; otherwise return -1.

Required number of digits is very large (e.g., 1000 digits), potentially leading to performance issues.

How to Handle:

Use string manipulation and avoid unnecessary numeric conversions to optimize performance for large numbers of digits.

No palindrome exists for the required number of digits divisible by K (e.g., searching for a 2-digit palindrome divisible by 7 which doesn't exist larger than 9000).

How to Handle:

Return -1 when the iteration reaches the smallest possible palindrome for the given number of digits.

Integer overflow during intermediate calculations (e.g., when calculating the product of digits or when constructing palindromes).

How to Handle:

Use string-based palindrome construction and modular arithmetic when checking divisibility to prevent overflow.

K is a very large number

How to Handle:

The search space can be reduced by first considering the largest possible palindrome for the given digits, and check its divisibility by K.

The solution fails to create the largest number after selecting the prefix.

How to Handle:

Ensure that the palindrome is constructed correctly by mirroring the prefix in reverse order around the middle point of the number.