Largest Palindrome That Is a Multiple

Hard

You are given digits and divisor. Find the largest number with exactly digits digits (no leading zeros) that reads the same in both directions and is divisible by divisor. Return it as a string, since the number can be very long.

Example 1

digits=3, divisor=4 → '888'

A three-digit palindrome is divisible by 4 only if its last two digits form a multiple of 4, and its first digit equals the last one. The best choice is 888.

Example 2

digits=2, divisor=7 → '77'

The two-digit palindromes are 11, 22, …, 99, and only 77 is divisible by 7.

Example 3

digits=4, divisor=5 → '5995'

A multiple of 5 without a leading zero has to end in 5, so it also starts with 5. The middle can be all nines: 5995.

Constraints

1 ≤ digits ≤ 10⁵
1 ≤ divisor ≤ 9

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Math String Dynamic Programming Number Theory

Similar problems

Zero-Free Number With a Multiple Digit Product Hard Chunks With a Common Divisor Medium Does the Text Fit the Pattern Hard Numbers From Working Keys Hard Mirror Chunk Split Hard

Input

digits=3, divisor=4

Expected

'888'

Run checks the first 3 tests in your browser. Submit checks all 52 tests on the server, hidden ones included.