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.An integer is called good if its digits can be rearranged to form a k-palindromic integer. For example, for k = 2, 2020 can be rearranged to form the k-palindromic integer 2002, whereas 1010 cannot be rearranged to form a k-palindromic integer.
Return the count of good integers containing n digits.
Note that any integer must not have leading zeros, neither before nor after rearrangement. For example, 1010 cannot be rearranged to form 101.
Example 1:
Input: n = 3, k = 5
Output: 27
Explanation:
Some of the good integers are:
Example 2:
Input: n = 1, k = 4
Output: 2
Explanation:
The two good integers are 4 and 8.
Example 3:
Input: n = 5, k = 6
Output: 2468
Constraints:
1 <= n <= 101 <= k <= 9This approach uses backtracking to generate all possible k-palindromic integers with n digits. It checks if a number can be rearranged into such a structure.
The code generates numbers with a given number of digits and checks if they are k-palindromic. It converges by backtracking through all possible numbers.
C++
Java
Python
C#
JavaScript
Time complexity is O(9^n), and space complexity is O(n) due to the recursion stack.
This approach sets up a Dynamic Programming (DP) table to store solutions of sub-problems involving palindromicity checks and divisibility, reducing repetition.
Implementing the Dynamic Programming approach in C involves understanding prior states and calculations, focusing on efficient combination management and k-palindromicity checks.
C++
Java
Python
C#
JavaScript
Time complexity and space complexity would depend on sub-problem calculations saving substantial reduction from naive method.
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time complexity is O(9^n), and space complexity is O(n) due to the recursion stack. |
| Dynamic Programming Approach | Time complexity and space complexity would depend on sub-problem calculations saving substantial reduction from naive method. |
Microsoft's Most Asked Question 2021 - Count Good Nodes in a Binary Tree - Leetcode 1448 - Python • NeetCode • 111,386 views views
Watch 9 more video solutions →Practice Find the Count of Good Integers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor