Find the Largest Palindrome Divisible by K

Find the Largest Palindrome Divisible by K - Problem

Math String Dynamic Programming Greedy Number Theory Hard

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.

Input & Output

Example 1 — Basic Case

$ Input: n = 3, k = 5

› Output: 595

💡 Note: Need 3-digit palindrome divisible by 5. Since divisible by 5 requires last digit 0 or 5, and palindrome means first=last, we need first=last=5. To maximize, set middle=9. Result: 595.

Example 2 — Single Digit

$ Input: n = 1, k = 4

› Output: 8

💡 Note: Need largest 1-digit number divisible by 4. The largest is 8 (8÷4=2).

Example 3 — Even Length

$ Input: n = 4, k = 6

› Output: 8778

💡 Note: Need 4-digit palindrome divisible by 6. Must be divisible by both 2 and 3. Try largest possible: 8778. Sum of digits: 8+7+7+8=30, divisible by 3 ✓. Last digit 8 is even ✓. 8778÷6=1463 ✓.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ k ≤ 9

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

n=3 digits, k=5 (divisible by 5)

Apply Constraints

Palindrome + divisible by 5 + maximize

Construct Answer

Result: 595

Key Takeaway

🎯 Key Insight: Use divisibility rules to constrain digit choices, then maximize within those constraints

Asked in

G Google 42 a Amazon 38 M Microsoft 35 f Meta 28

The key insight is to use mathematical properties of divisibility rules and palindrome constraints to construct the answer efficiently. For special cases like k=1,2,5, we can directly construct the optimal palindrome. The mathematical optimization approach runs in O(n) time and O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(10^n)	O(1)	Generate all possible palindromes and check divisibility
Greedy Construction	O(n * 10)	O(n)	Build palindrome greedily by choosing largest possible digits
Mathematical Optimization	O(n)	O(n)	Use number theory and modular arithmetic for efficient construction

Brute Force — Algorithm Steps

Start from largest n-digit number (999...9)
For each number, check if palindrome
Check if divisible by k
Return first valid number

Visualization

Tap to expand

Step-by-Step Walkthrough

Start from 999

Begin with largest 3-digit number

Check conditions

Verify palindrome and divisibility

Found answer

Return first valid number

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int isPalindrome(char* s) {
    int len = strlen(s);
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return 0;
        }
    }
    return 1;
}

char* solution(int n, int k) {
    // Start from largest n-digit number
    long long start = (long long)pow(10, n - 1);
    long long end = (long long)pow(10, n) - 1;
    
    char* result = malloc(20);
    
    // Work backwards from largest
    for (long long num = end; num >= start; num--) {
        sprintf(result, "%lld", num);
        if (isPalindrome(result) && num % k == 0) {
            return result;
        }
    }
    
    strcpy(result, "-1");
    return result;
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    
    char* result = solution(n, k);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(10^n)

In worst case, may need to check exponentially many numbers

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler