Find the count of good integers

Hash Table Math Combinatorics Enumeration

69.5% acceptance

Feb 25, 2026

463

112

You are given two positive integers n and k. An integer x is k-palindromic if it's a palindrome and divisible by k. An integer is "good" if its digits can be rearranged to form a k-palindromic integer. Return the count of good n-digit integers.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_good_integers(n: i32, k: i32) -> i64 {
    let n = n as usize;
    let k = k as i64;
    let h = (n + 1) / 2;
    let mut seen: std::collections::HashSet<[u8; 10]> = std::collections::HashSet::new();
    let mut ans: i64 = 0;

    // Enumerate all k-palindromes with n digits
    // A palindrome is determined by its first h digits
    let lo = 10i64.pow((h - 1) as u32);
    let hi = 10i64.pow(h as u32);
    for half in lo..hi {
      // Build palindrome
      let half_s = format!("{}", half);
      let half_b = half_s.as_bytes();
      let rev_start = if n % 2 == 1 { h - 1 } else { h };
      let full: String = half_s
        .chars()
        .chain(half_b[..rev_start].iter().rev().map(|&b| b as char))
        .collect();
      let val: i64 = full.parse().unwrap();
      if val % k != 0 {
        continue;
      }
      // Count permutations of this multiset that are n-digit numbers
      let mut freq = [0u8; 10];
      for ch in full.bytes() {
        freq[(ch - b'0') as usize] += 1;
      }
      if seen.contains(&freq) {
        continue;
      }
      seen.insert(freq);
      // Number of n-digit permutations with this digit multiset
      ans += Self::count_perms(&freq, n);
    }
    ans
  }

  fn count_perms(freq: &[u8; 10], n: usize) -> i64 {
    // Total permutations = n! / (f0! * f1! * ... * f9!)
    // Minus permutations with leading zero = (n-1)! / ((f0-1)! * f1! * ... * f9!) if f0 > 0
    let factorial = |x: usize| -> i64 {
      let mut r = 1i64;
      for i in 2..=x {
        r *= i as i64;
      }
      r
    };
    let denom: i64 = freq.iter().map(|&f| factorial(f as usize)).product();
    let total = factorial(n) / denom;
    // Leading zeros: choose a leading zero means one leading digit is 0
    let leading_zero = if freq[0] > 0 {
      let mut freq2 = *freq;
      freq2[0] -= 1;
      let denom2: i64 = freq2.iter().map(|&f| factorial(f as usize)).product();
      factorial(n - 1) / denom2
    } else {
      0
    };
    total - leading_zero
  }
}