Sum of k-Mirror Numbers

Problem

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.

Examples

Example 1

Input: k = 2, n = 5
Output: 25
Explanation: The 5 smallest 2-mirror numbers and their representations in base-2 are listed as follows:
  base-10    base-2
    1          1
    3          11
    5          101
    7          111
    9          1001
Their sum = 1 + 3 + 5 + 7 + 9 = 25. 

Example 2

Input: k = 3, n = 7
Output: 499
Explanation: The 7 smallest 3-mirror numbers are and their representations in base-3 are listed as follows:
  base-10    base-3
    1          1
    2          2
    4          11
    8          22
    121        11111
    151        12121
    212        21212
Their sum = 1 + 2 + 4 + 8 + 121 + 151 + 212 = 499.

Example 3

Input: k = 7, n = 17
Output: 20379000
Explanation: The 17 smallest 7-mirror numbers are:
1, 2, 3, 4, 5, 6, 8, 121, 171, 242, 292, 16561, 65656, 2137312, 4602064, 6597956, 6958596

Constraints

• 2 <= k <= 9
• 1 <= n <= 30

Solution

Method 1 – Palindrome Enumeration with Base Conversion

Intuition

A k-mirror number is a palindrome in both base-10 and base-k. Since palindromes are rare, we can generate all base-10 palindromes in increasing order and check if their base-k representation is also a palindrome. This ensures we find the smallest k-mirror numbers efficiently.

Approach

1. Initialize an empty list to store found k-mirror numbers.
2. Generate palindromic numbers in base-10, starting from the smallest (single-digit) and increasing length.
3. For each palindrome:

• Convert it to base-k.
• Check if the base-k representation is also a palindrome.
• If yes, add it to the answer list.

4. Continue until n k-mirror numbers are found.
5. Return the sum of the first n k-mirror numbers.

Edge cases:

• Handle both odd and even length palindromes.
• Ensure no leading zeros in generated palindromes.

Code

C++

class Solution {
public:
   long long kMirror(int k, int n) {
      vector<long long> ans;
      for (int len = 1; ans.size() < n; ++len) {
        for (int half = pow(10, (len - 1) / 2); half < pow(10, (len + 1) / 2) && ans.size() < n; ++half) {
           string s = to_string(half);
           string rev = s;
           reverse(rev.begin(), rev.end());
           string pal = s + rev.substr(len % 2);
           long long num = stoll(pal);
           vector<int> basek;
           long long tmp = num;
           while (tmp) {
              basek.push_back(tmp % k);
              tmp /= k;
           }
           if (equal(basek.begin(), basek.end(), basek.rbegin()))
              ans.push_back(num);
        }
      }
      long long sum = 0;
      for (auto x : ans) sum += x;
      return sum;
   }
};

Go

func kMirror(k int, n int) int64 {
   ans := []int64{}
   for l := 1; len(ans) < n; l++ {
      start := intPow(10, (l-1)/2)
      end := intPow(10, (l+1)/2)
      for half := start; half < end && len(ans) < n; half++ {
        s := strconv.Itoa(half)
        rev := reverseStr(s)
        pal := s + rev
        if l%2 == 1 {
           pal = s + rev[1:]
        }
        num, _ := strconv.ParseInt(pal, 10, 64)
        if isPalindrome(baseK(num, k)) {
           ans = append(ans, num)
        }
      }
   }
   var sum int64
   for _, v := range ans {
      sum += v
   }
   return sum
}

func intPow(a, b int) int {
   res := 1
   for b > 0 {
      res *= a
      b--
   }
   return res
}

func reverseStr(s string) string {
   b := []byte(s)
   for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
      b[i], b[j] = b[j], b[i]
   }
   return string(b)
}

func baseK(num int64, k int) []int {
   res := []int{}
   for num > 0 {
      res = append(res, int(num%int64(k)))
      num /= int64(k)
   }
   return res
}

func isPalindrome(arr []int) bool {
   for i, j := 0, len(arr)-1; i < j; i, j = i+1, j-1 {
      if arr[i] != arr[j] {
        return false
      }
   }
   return true
}

Java

class Solution {
   public long kMirror(int k, int n) {
      List<Long> ans = new ArrayList<>();
      for (int len = 1; ans.size() < n; ++len) {
        int start = (int)Math.pow(10, (len - 1) / 2);
        int end = (int)Math.pow(10, (len + 1) / 2);
        for (int half = start; half < end && ans.size() < n; ++half) {
           String s = Integer.toString(half);
           StringBuilder rev = new StringBuilder(s).reverse();
           String pal = s + rev.substring(len % 2);
           long num = Long.parseLong(pal);
           if (isKPalindrome(num, k)) {
              ans.add(num);
           }
        }
      }
      long sum = 0;
      for (long x : ans) sum += x;
      return sum;
   }
   private boolean isKPalindrome(long num, int k) {
      List<Integer> digits = new ArrayList<>();
      while (num > 0) {
        digits.add((int)(num % k));
        num /= k;
      }
      for (int i = 0, j = digits.size() - 1; i < j; ++i, --j) {
        if (!digits.get(i).equals(digits.get(j))) return false;
      }
      return true;
   }
}

Kotlin

class Solution {
   fun kMirror(k: Int, n: Int): Long {
      val ans = mutableListOf<Long>()
      var len = 1
      while (ans.size < n) {
        val start = Math.pow(10.0, ((len - 1) / 2).toDouble()).toInt()
        val end = Math.pow(10.0, ((len + 1) / 2).toDouble()).toInt()
        for (half in start until end) {
           if (ans.size >= n) break
           val s = half.toString()
           val rev = s.reversed()
           val pal = s + rev.substring(len % 2)
           val num = pal.toLong()
           if (isKPalindrome(num, k)) {
              ans.add(num)
           }
        }
        len++
      }
      return ans.sum()
   }
   private fun isKPalindrome(num: Long, k: Int): Boolean {
      val digits = mutableListOf<Int>()
      var n = num
      while (n > 0) {
        digits.add((n % k).toInt())
        n /= k
      }
      return digits == digits.reversed()
   }
}

Python

class Solution:
   def kMirror(self, k: int, n: int) -> int:
      def is_k_palindrome(x: int) -> bool:
        arr = []
        while x:
           arr.append(x % k)
           x //= k
        return arr == arr[::-1]

      ans: list[int] = []
      length = 1
      while len(ans) < n:
        for half in range(10 ** ((length - 1) // 2), 10 ** ((length + 1) // 2)):
           s = str(half)
           pal = s + s[-2::-1] if length % 2 else s + s[::-1]
           num = int(pal)
           if is_k_palindrome(num):
              ans.append(num)
           if len(ans) == n:
              break
        length += 1
      return sum(ans)

Rust

impl Solution {
   pub fn k_mirror(k: i32, n: i32) -> i64 {
      fn is_k_palindrome(mut x: i64, k: i32) -> bool {
        let mut arr = vec![];
        while x > 0 {
           arr.push((x % k as i64) as i32);
           x /= k as i64;
        }
        arr.iter().eq(arr.iter().rev())
      }
      let mut ans = vec![];
      let mut len = 1;
      while ans.len() < n as usize {
        let start = 10_i64.pow(((len - 1) / 2) as u32);
        let end = 10_i64.pow(((len + 1) / 2) as u32);
        for half in start..end {
           let s = half.to_string();
           let pal = if len % 2 == 0 {
              format!("{}{}", s, s.chars().rev().collect::<String>())
           } else {
              format!("{}{}", s, s.chars().rev().skip(1).collect::<String>())
           };
           let num = pal.parse::<i64>().unwrap();
           if is_k_palindrome(num, k) {
              ans.push(num);
           }
           if ans.len() == n as usize {
              break;
           }
        }
        len += 1;
      }
      ans.iter().sum()
   }
}

Complexity

• ⏰ Time complexity: O(n * L * log_k(M)), where L is the length of palindromes needed and M is the largest k-mirror number found.
• 🧺 Space complexity: O(n + L), for storing results and temporary palindrome representations.