Sum of k mirror numbers

Math Enumeration

63.8% acceptance

Feb 25, 2026

429

210

A k-mirror number is a positive integer without leading zeros that reads the same both forward and backward in base-10 as well as in base-k. For example, 9 is a 2-mirror number. The representation of 9 in base-10 and base-2 are 9 and 1001 respectively, which read the same both forward and backward. On the contrary, 4 is not a 2-mirror number. The representation of 4 in base-2 is 100, which does not read the same both forward and backward. Given the base k and the number n, return the sum of the n smallest k-mirror numbers.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn k_mirror(k: i32, n: i32) -> i64 {
    let k = k as i64;
    let n = n as usize;
    let mut count = 0;
    let mut sum = 0i64;

    // Generate base-10 palindromes in increasing order by length
    let mut length = 1usize;
    'outer: loop {
      let half_len = (length + 1) / 2;
      let start = if half_len == 1 { 1i64 } else { 10i64.pow((half_len - 1) as u32) };
      let end = 10i64.pow(half_len as u32);

      for half in start..end {
        // Build palindrome string
        let s = half.to_string();
        let mut pal_str = s.clone();
        if length % 2 == 1 {
          // Odd length: mirror all but last char
          let rev: String = s[..s.len() - 1].chars().rev().collect();
          pal_str.push_str(&rev);
        } else {
          // Even length: mirror all chars
          let rev: String = s.chars().rev().collect();
          pal_str.push_str(&rev);
        }
        let pal: i64 = pal_str.parse().unwrap();

        // Check if palindrome in base k
        if Self::is_base_k_palindrome(pal, k) {
          count += 1;
          sum += pal;
          if count == n {
            break 'outer;
          }
        }
      }
      length += 1;
    }

    sum
  }

  fn is_base_k_palindrome(mut num: i64, k: i64) -> bool {
    let mut digits = Vec::new();
    while num > 0 {
      digits.push(num % k);
      num /= k;
    }
    let rev: Vec<i64> = digits.iter().rev().cloned().collect();
    digits == rev
  }
}