50 lines
1.4 KiB
Kotlin
50 lines
1.4 KiB
Kotlin
class Solution {
|
|
private fun precomputeFactorial(n: Int): LongArray =
|
|
LongArray(n + 1) { 1 }.let { fs ->
|
|
(1..n).forEach { i ->
|
|
fs[i] = fs[i - 1] * i
|
|
}
|
|
|
|
fs
|
|
}
|
|
|
|
private fun countDigits(s: String): IntArray =
|
|
IntArray(10).let { digit ->
|
|
s.toCharArray().forEach { digit[it - '0']++ }
|
|
digit
|
|
}
|
|
|
|
private fun getPalindromes(
|
|
n: Int,
|
|
k: Int,
|
|
): Set<String> =
|
|
buildSet {
|
|
val base = (1..(n - 1) / 2).fold(1) { acc, _ -> acc * 10 }
|
|
val skip = n.and(1)
|
|
|
|
(base..10 * base - 1)
|
|
.map { i ->
|
|
var s = i.toString()
|
|
s += StringBuilder(s).reverse().substring(skip)
|
|
s to s.toLong()
|
|
}.filter { (_, it) -> it % k == 0L }
|
|
.forEach { (it, _) ->
|
|
val chars = it.toCharArray()
|
|
chars.sort()
|
|
add(String(chars))
|
|
}
|
|
}
|
|
|
|
fun countGoodIntegers(
|
|
n: Int,
|
|
k: Int,
|
|
): Long =
|
|
precomputeFactorial(n).let { factorial ->
|
|
getPalindromes(n, k).sumOf { s ->
|
|
val digit = countDigits(s)
|
|
val total = (n - digit[0]) * factorial[n - 1]
|
|
|
|
digit.fold(total) { total, count -> total / factorial[count] }
|
|
}
|
|
}
|
|
}
|