3260. Find the Largest Palindrome Divisible by K LeetCode Solution
In this guide, you will get 3260. Find the Largest Palindrome Divisible by K LeetCode Solution with the best time and space complexity. The solution to Find the Largest Palindrome Divisible by K problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Find the Largest Palindrome Divisible by K solution in C++
- Find the Largest Palindrome Divisible by K solution in Java
- Find the Largest Palindrome Divisible by K solution in Python
- Additional Resources
Problem Statement of Find the Largest Palindrome Divisible by K
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 <= 105
1 <= k <= 9
Complexity Analysis
- Time Complexity: O(\log n)
- Space Complexity: O(\log n)
3260. Find the Largest Palindrome Divisible by K LeetCode Solution in C++
class Solution {
public:
string largestPalindrome(int n, int k) {
switch (k) {
case 1:
return string(n, '9');
case 2:
return n <= 2 ? string(n, '8') : "8" + string(n - 2, '9') + "8";
case 3:
case 9:
return string(n, '9');
case 4:
return n <= 4 ? string(n, '8') : "88" + string(n - 4, '9') + "88";
case 5:
return n <= 2 ? string(n, '5') : "5" + string(n - 2, '9') + "5";
case 6:
if (n <= 2) {
return string(n, '6');
} else if (n % 2 == 1) {
const int l = n / 2 - 1;
return "8" + string(l, '9') + "8" + string(l, '9') + "8";
} else {
const int l = n / 2 - 2;
return "8" + string(l, '9') + "77" + string(l, '9') + "8";
}
case 8:
return n <= 6 ? string(n, '8') : "888" + string(n - 6, '9') + "888";
default:
const string middle[] = {"", "7", "77",
"959", "9779", "99799",
"999999", "9994999", "99944999",
"999969999", "9999449999", "99999499999"};
const int q = n / 12;
const int r = n % 12;
return string(q * 6, '9') + middle[r] + string(q * 6, '9');
}
}
};
/* code provided by PROGIEZ */3260. Find the Largest Palindrome Divisible by K LeetCode Solution in Java
class Solution {
public String largestPalindrome(int n, int k) {
StringBuilder sb = new StringBuilder();
switch (k) {
case 1:
return "9".repeat(n);
case 2:
return n <= 2 ? "8".repeat(n)
: sb.append("8") //
.append("9".repeat(n - 2))
.append("8")
.toString();
case 3:
case 9:
return "9".repeat(n);
case 4:
return n <= 4 ? "8".repeat(n)
: sb.append("88") //
.append("9".repeat(n - 4))
.append("88")
.toString();
case 5:
return n <= 2 ? "5".repeat(n)
: sb.append("5") //
.append("9".repeat(n - 2))
.append("5")
.toString();
case 6:
if (n <= 2) {
return "6".repeat(n);
} else if (n % 2 == 1) {
final int l = n / 2 - 1;
return sb.append("8")
.append("9".repeat(l))
.append("8")
.append("9".repeat(l))
.append("8")
.toString();
} else {
final int l = n / 2 - 2;
return sb.append("8")
.append("9".repeat(l))
.append("77")
.append("9".repeat(l))
.append("8")
.toString();
}
case 8:
return n <= 6 ? "8".repeat(n)
: sb.append("888") //
.append("9".repeat(n - 6))
.append("888")
.toString();
default:
String[] middle = {"", "7", "77", "959",
"9779", "99799", "999999", "9994999",
"99944999", "999969999", "9999449999", "99999499999"};
final int q = n / 12;
final int r = n % 12;
return sb.append("999999".repeat(q))
.append(middle[r])
.append("999999".repeat(q))
.toString();
}
}
}
// code provided by PROGIEZ3260. Find the Largest Palindrome Divisible by K LeetCode Solution in Python
class Solution:
def largestPalindrome(self, n: int, k: int) -> str:
match k:
case 1:
return '9' * n
case 2:
return '8' * n if n <= 2 else '8' + '9' * (n - 2) + '8'
case 3 | 9:
return '9' * n
case 4:
return '8' * n if n <= 4 else '88' + '9' * (n - 4) + '88'
case 5:
return '5' * n if n <= 2 else '5' + '9' * (n - 2) + '5'
case 6:
if n <= 2:
return '6' * n
elif n % 2 == 1:
l = n // 2 - 1
return '8' + '9' * l + '8' + '9' * l + '8'
else:
l = n // 2 - 2
return '8' + '9' * l + '77' + '9' * l + '8'
case 8:
return '8' * n if n <= 6 else '888' + '9' * (n - 6) + '888'
case _:
middle = {
: '', 1: '7', 2: '77', 3: '959', 4: '9779', 5: '99799',
: '999999', 7: '9994999', 8: '99944999', 9: '999969999',
: '9999449999', 11: '99999499999'
}
q, r = divmod(n, 12)
return '999999' * q + middle[r] + '999999' * q
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.