Find the Largest Palindrome Divisible by K solution and explanation
Google
3 more videos on this problem
3260. Find the Largest Palindrome Divisible by K | Weekly Contest 411 | LeetCodePulkit Malhotra · 16:25 · 1K views
3260. Find the Largest Palindrome Divisible by K | Digit DPTech Courses · 15:01 · 1K views
3260. Find the Largest Palindrome Divisible by K (Leetcode Hard)Programming Live with Larry · 1:02:31 · 621 views
LeetCode Weekly Contest 411 | Find the Largest Palindrome Divisible by KSmart Interviews · 51:30 · 474 views
The problem
You are given two positive integers n and k.
An integer x is called k-palindromic if:
xis a palindrome.xis divisible byk.
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 <= 1051 <= k <= 9
Approach overview
Problem Overview: You are given the number of digits n and an integer k. The task is to construct the largest n-digit palindrome whose numeric value is divisible by k. Since the result can be extremely large, the solution focuses on building the palindrome as a string while controlling the remainder using modular arithmetic.
Approach 1: Reverse Check Starting Approach (Brute Force) (Time: O(10^(n/2) * n), Space: O(n))
Start from the largest possible n-digit palindrome and move downward until you find one divisible by k. A palindrome is defined by its first half, so generate candidates by decreasing the first half and mirroring it to form the full number. For each generated palindrome, compute value % k. If the remainder is zero, you found the answer. This approach is straightforward and demonstrates the brute-force search space, but the number of candidates grows exponentially with n/2, making it impractical for large inputs.
Approach 2: Iterative Palindrome Construction (Greedy + DP on Remainders) (Time: O(n * k * 10), Space: O(n * k))
Instead of checking every palindrome, construct the number digit by digit from the outside toward the center. Each position contributes a weighted value modulo k. Precompute powers of 10 modulo k using number theory. Then use dynamic programming on the remainder state: track whether the remaining positions can still produce a valid total remainder of 0. For each symmetric digit pair, try digits from 9 down to 0 (greedy for the largest result). Choose the largest digit that still allows a valid remainder path according to the DP table. For odd-length palindromes, handle the middle digit separately. This strategy guarantees the lexicographically largest palindrome while maintaining divisibility.
Recommended for interviews: The iterative palindrome construction approach is the one interviewers expect. It combines mod k arithmetic, greedy digit selection, and dynamic programming to prune impossible states. Showing the brute-force palindrome enumeration first demonstrates understanding of the search space, but implementing the remainder-based DP proves you can optimize exponential generation into a controlled O(n * k) state exploration.
Approach 1: Iterative Palindrome Construction
This approach involves starting from the largest n-digit number and iteratively constructing a palindrome while checking for divisibility by k. For even-digit palindromes, half the digits determine the rest, while for odd digits, one central digit can vary. Generate such numbers and check if they meet the conditions.
def largest_palindrome_divisible(n, k):
# Edge case for 1-digit numbers
if n == 1:
for num in range(9, 0, -1):
if num % k == 0:
return str(num)
return ""
max_num = int('9' * n)
min_num = 10 ** (n - 1)
for num in range(max_num, min_num - 1, -1):
str_num = str(num)
if str_num == str_num[::-1] and num % k == 0:
return str_num
return ""public class LargestPalindrome {
public static String largestPalindromeDivisible(int n, int k) {
if (n == 1) {
for (int num = 9; num > 0; num--) {
if (num % k == 0) {
return String.valueOf(num);
}
}
return "";
}
int maxNum = (int)Math.pow(10, n) - 1;
int minNum = (int)Math.pow(10, n - 1);
for (int num = maxNum; num >= minNum; num--) {
String strNum = String.valueOf(num);
String revNum = new StringBuilder(strNum).reverse().toString();
if (strNum.equals(revNum) && num % k == 0) {
return strNum;
}
}
return "";
}
}#include <iostream>
#include <string>
using namespace std;
string largest_palindrome_divisible(int n, int k) {
if (n == 1) {
for (int num = 9; num > 0; --num) {
if (num % k == 0) {
return to_string(num);
}
}
return "";
}
int max_num = pow(10, n) - 1;
int min_num = pow(10, n - 1);
for (int num = max_num; num >= min_num; --num) {
string str_num = to_string(num);
string rev_num(str_num.rbegin(), str_num.rend());
if (str_num == rev_num && num % k == 0) {
return str_num;
}
}
return "";
}function largestPalindromeDivisible(n, k) {
if (n === 1) {
for (let num = 9; num > 0; --num) {
if (num % k === 0) {
return num.toString();
}
}
return "";
}
let maxNum = Math.pow(10, n) - 1;
let minNum = Math.pow(10, n - 1);
for (let num = maxNum; num >= minNum; --num) {
let strNum = num.toString();
let revNum = strNum.split('').reverse().join('');
if (strNum === revNum && num % k === 0) {
return strNum;
}
}
return "";
}This Python function starts from the largest n-digit number and decrements until it finds a number that is both palindrome and divisible by k. It checks for palindromic property by comparing the string to its reverse.
Time Complexity: O(9 * 10^(n/2)), since we mostly check half the digits.
Space Complexity: O(1), aside from auxiliary storage for the palindrome check.
Approach 2: Reverse Check Starting Approach
This approach reverses the order of searching to construct the palindrome first and then check for divisibility. It can be more efficient in some cases where palindrome properties dictate prior elimination of candidates.
#include <stdio.h>
#include <string.h>
#include <math.h>
int is_palindrome(int num) {
char str[20];
sprintf(str, "%d", num);
int len = strlen(str);
for (int i = 0; i < len / 2; i++) {
if (str[i] != str[len - i - 1]) {
return 0;
}
}
return 1;
}
char* largest_palindrome_divisible(int n, int k, char *result) {
int max_num = pow(10, n) - 1;
int min_num = pow(10, n - 1);
for (int half = max_num; half >= min_num; --half) {
int palindrome_candidate = half * pow(10, n / 2) + reverse(half, n % 2);
if (palindrome_candidate % k == 0) {
sprintf(result, "%d", palindrome_candidate);
return result;
}
}
return "";
}
int reverse(int num, int is_odd) {
int rev = 0;
if (is_odd) num /= 10;
while (num > 0) {
rev = rev * 10 + num % 10;
num /= 10;
}
return rev;
}using System;
public class Solution {
public static string LargestPalindromeDivisible(int n, int k) {
int maxNum = (int)Math.Pow(10, n) - 1;
int minNum = (int)Math.Pow(10, n - 1);
for (int half = maxNum; half >= minNum; --half) {
var palindromeCandidate = int.Parse(half.ToString() + Reverse(half.ToString().Substring(n % 2)));
if (palindromeCandidate % k == 0) {
return palindromeCandidate.ToString();
}
}
return "";
}
public static string Reverse(string s) {
char[] charArray = s.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
}This C# code generates a palindrome for each half number iteratively, considering even and odd n values, then validates through divisibility.
Time Complexity: O(10^(n/2)).
Space Complexity: O(1).
Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Palindrome Construction | Time Complexity: O(9 * 10^(n/2)), since we mostly check half the digits. |
| Reverse Check Starting Approach | Time Complexity: O(10^(n/2)). |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Check Starting Approach | O(10^(n/2) * n) | O(n) | Small n or when demonstrating brute-force palindrome enumeration |
| Iterative Palindrome Construction (Greedy + DP) | O(n * k * 10) | O(n * k) | Large n where direct enumeration is infeasible; optimal interview solution |
Frequently asked questions
Is Find the Largest Palindrome Divisible by K easy or hard?
Find the Largest Palindrome Divisible by K is categorized as a Hard problem. The challenge comes from combining palindrome constraints with divisibility checks while avoiding large integer arithmetic, requiring dynamic programming with modular math.
Find the Largest Palindrome Divisible by K Python/Java solution
Most implementations construct the palindrome using a greedy loop and remainder DP. Python uses lists or strings for building the result, while Java or C++ often use character arrays. The logic remains the same: track modulo contributions and choose the largest valid digit at each step.
How to solve Find the Largest Palindrome Divisible by K in O(n)?
Pure O(n) is generally not achievable because the algorithm must consider remainder states modulo k. The practical optimal solution is O(n * k * 10), where you precompute powers of 10 modulo k and use DP to determine whether remaining positions can achieve remainder 0. Greedy digit selection ensures the final palindrome is the largest.
What is the best approach for Find the Largest Palindrome Divisible by K?
The most efficient approach builds the palindrome digit by digit while tracking remainders modulo k. Using greedy selection (try digits from 9 down to 0) combined with dynamic programming on remainder states ensures the largest possible palindrome is constructed. This method runs in O(n * k * 10) time and avoids enumerating all palindromes.
Is Find the Largest Palindrome Divisible by K asked at Google/Amazon/Meta?
Problems combining palindrome construction with modular arithmetic and greedy digit selection frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of number theory, remainder propagation, and building large numbers without integer overflow.
What data structure is used in Find the Largest Palindrome Divisible by K?
The solution mainly uses strings or character arrays to construct the palindrome and a dynamic programming table that tracks reachable remainders modulo k. Precomputed arrays for powers of 10 modulo k are also used to calculate digit contributions efficiently.
What is the time complexity of Find the Largest Palindrome Divisible by K?
The optimized greedy + DP approach runs in O(n * k * 10) time and O(n * k) space because each position in the palindrome evaluates up to 10 digit choices while tracking k possible remainders. A brute-force enumeration approach can take O(10^(n/2) * n) time since it generates and checks many palindromes.