3727. Find the Count of Good Integers
Intuition
- For a palindromic number, we only need to determine the first half of digits, as the second half is a mirror
- We need to handle odd and even length numbers differently
- We need to avoid counting duplicates when different digit combinations result in the same frequency pattern
- Leading zeros should be excluded from the count
Approach
- Generate palindromic numbers by:
- Only generating the first half (up to breakPoint)
- Mirroring the digits for the second half
- For odd length numbers, the middle digit is counted once
- Use a frequency array to track digit counts and avoid duplicates:
- Store the frequency of each digit (0-9) in a [10]int array
- Use this as a key in a map to avoid counting duplicate patterns
- Calculate permutations for each valid pattern:
- Use factorial to compute total possible arrangements
- Account for repeated digits by dividing by their factorials
- Handle leading zeros by subtracting invalid cases
- Recursively generate all possible first halves and check:
- If the resulting palindrome is divisible by k
- If we've seen this digit frequency pattern before
Complexity
- Time complexity: O(10^(n/2) * n)
- Space complexity: O(n)
Keywords
- Palindrome
- Combinatorics
- Recursion
- Permutation
- Factorial
Code
func countGoodIntegers(n int, k int) int64 {
cnt := int64(0)
number, record, breakPoint, fac := make([]rune, n), make(map[[10]int]bool), 0, make(map[int]int)
switch n & 1 == 1 {
case true:
breakPoint = n / 2
case false:
breakPoint = n / 2 - 1
}
fac[0] = 1
for i := 1; i <= n; i += 1 {
fac[i] = fac[i - 1] * i
}
getPalindromic := func(cur []rune) [10]int {
ret := [10]int{}
for i := 0; i <= breakPoint; i += 1 {
cur[len(cur) - 1 - i] = cur[i]
ret[cur[i] - '0'] += 2
}
if n & 1 == 1 {
ret[cur[breakPoint] - '0'] -= 1
}
return ret
}
countPermutations := func(rec [10]int) int {
total := fac[n]
for _, ii := range rec {
total /= fac[ii]
}
if rec[0] != 0 {
total -= ((total * fac[rec[0]] / n) / fac[rec[0] - 1])
}
return total
}
var recur func(cur []rune, i int, nextN rune)
recur = func(cur []rune, i int, nextN rune) {
if i > breakPoint {
return
}
cur[i] = nextN
if i == breakPoint {
rec := getPalindromic(cur)
if _, exist := record[rec]; exist {
return
}
palindromicNumber, _ := strconv.Atoi(string(cur))
if palindromicNumber % k != 0 {
return
}
cnt, record[rec] = cnt + int64(countPermutations(rec)), true
return
}
for j := 0; j <= 9; j += 1 {
recur(number, i + 1, rune('0' + j))
}
}
for i := 1; i <= 9; i += 1 {
recur(number, 0, rune('0' + i))
}
return cnt
}