3272. Find the Count of Good Integers LeetCode Solution
In this guide, you will get 3272. Find the Count of Good Integers LeetCode Solution with the best time and space complexity. The solution to Find the Count of Good Integers 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.
Problem Statement of Find the Count of Good Integers
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:
551 because it can be rearranged to form 515.
525 because it is already k-palindromic.
Example 2:
Input: n = 1, k = 4
Output: 2
Explanation:
The two good integers are 4 and 8.
3272. Find the Count of Good Integers LeetCode Solution in C++
class Solution {
public:
long long countGoodIntegers(int n, int k) {
const int halfLength = (n + 1) / 2;
const int minHalf = pow(10, halfLength - 1);
const int maxHalf = pow(10, halfLength);
long ans = 0;
unordered_set<string> seen;
for (int num = minHalf; num < maxHalf; ++num) {
const string firstHalf = to_string(num);
const string secondHalf = {firstHalf.rbegin(), firstHalf.rend()};
const string palindrome = firstHalf + secondHalf.substr(n % 2);
if (stol(palindrome) % k != 0)
continue;
string sortedDigits = palindrome;
ranges::sort(sortedDigits);
if (seen.contains(sortedDigits))
continue;
seen.insert(sortedDigits);
vector<int> digitCount(10);
for (const char c : palindrome)
++digitCount[c - '0'];
// Leading zeros are not allowed, so the first digit is special.
const int firstDigitChoices = n - digitCount[0];
long permutations = firstDigitChoices * factorial(n - 1);
// For each repeated digit, divide by the factorial of the frequency since
// permutations that swap identical digits don't create a new number.
for (const int freq : digitCount)
if (freq > 1)
permutations /= factorial(freq);
ans += permutations;
}
return ans;
}
private:
long factorial(int n) {
long res = 1;
for (int i = 2; i <= n; ++i)
res *= i;
return res;
}
}; /* code provided by PROGIEZ */
3272. Find the Count of Good Integers LeetCode Solution in Java
class Solution {
public long countGoodIntegers(int n, int k) {
final int halfLength = (n + 1) / 2;
final int minHalf = (int) Math.pow(10, halfLength - 1);
final int maxHalf = (int) Math.pow(10, halfLength);
long ans = 0;
Set<String> seen = new HashSet<>();
for (int num = minHalf; num < maxHalf; ++num) {
final String firstHalf = String.valueOf(num);
final String secondHalf = new StringBuilder(firstHalf).reverse().toString();
final String palindrome = firstHalf + secondHalf.substring(n % 2);
if (Long.parseLong(palindrome) % k != 0)
continue;
char[] sortedDigits = palindrome.toCharArray();
Arrays.sort(sortedDigits);
String sortedDigitsStr = new String(sortedDigits);
if (seen.contains(sortedDigitsStr))
continue;
seen.add(sortedDigitsStr);
int[] digitCount = new int[10];
for (char c : palindrome.toCharArray())
++digitCount[c - '0'];
// Leading zeros are not allowed, so the first digit is special.
final int firstDigitChoices = n - digitCount[0];
long permutations = firstDigitChoices * factorial(n - 1);
// For each repeated digit, divide by the factorial of the frequency since
// permutations that swap identical digits don't create a new number.
for (final int freq : digitCount)
if (freq > 1)
permutations /= factorial(freq);
ans += permutations;
}
return ans;
}
private long factorial(int n) {
long res = 1;
for (int i = 2; i <= n; ++i)
res *= i;
return res;
}
} // code provided by PROGIEZ
3272. Find the Count of Good Integers LeetCode Solution in Python
class Solution:
def countGoodIntegers(self, n: int, k: int) -> int:
halfLength = (n + 1) // 2
minHalf = 10**(halfLength - 1)
maxHalf = 10**halfLength
ans = 0
seen = set()
for num in range(minHalf, maxHalf):
palindrome = str(num) + str(num)[::-1][n % 2:]
sortedDigits = ''.join(sorted(palindrome))
if int(palindrome) % k != 0 or sortedDigits in seen:
continue
seen.add(sortedDigits)
digitCount = collections.Counter(palindrome)
# Leading zeros are not allowed, so the first digit is special.
firstDigitChoices = n - digitCount['0']
permutations = firstDigitChoices * math.factorial(n - 1)
# For each repeated digit, divide by the factorial of the frequency since
# permutations that swap identical digits don't create a new number.
for freq in digitCount.values():
permutations //= math.factorial(freq)
ans += permutations
return ans # code by PROGIEZ
