We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Largest Palindrome Divisible by K

Difficulty: Hard

Problem Description

You are given two positive integers n and k. An integer x is called k-palindromic if it is a palindrome and 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.

Key Insights

  • A palindrome reads the same forwards and backwards.
  • The largest n-digit number is 10^n - 1.
  • To find the largest k-palindromic number, start from the largest n-digit palindrome and check for divisibility by k.
  • Palindromes can be generated efficiently by mirroring the first half of the digits.
  • The palindrome must be checked for divisibility in descending order to ensure the largest value.

Space and Time Complexity

Time Complexity: O(n) - Checking each palindrome and generating them efficiently. Space Complexity: O(1) - Only a few variables are used for storing results.

Solution

To solve the problem, we can generate palindromic numbers starting from the largest n-digit number and check each one for divisibility by k. The algorithm involves:

  1. Constructing the largest n-digit number.
  2. Iterating downwards to find the largest palindrome that meets the criteria.
  3. Utilizing string manipulation to check for palindromes.

Code Solutions

def largest_palindrome(n, k):
    # Start with the largest n-digit number
    max_num = 10**n - 1
    
    # Function to check if a number is a palindrome
    def is_palindrome(num):
        return str(num) == str(num)[::-1]
    
    # Iterate downwards from the largest number
    for num in range(max_num, 10**(n-1) - 1, -1):
        if num % k == 0 and is_palindrome(num):
            return str(num)

# Example usage
print(largest_palindrome(3, 5))  # Output: "595"
← Back to All Questions