🏂 Beginner-Friendly Guide: "Sum of k-Mirror Numbers" – LeetCode 2081 (C++| JavaScript | Python )

#programming #cpp #javascript #python

👋 Introduction
In the world of programming puzzles, palindrome-based problems always offer a unique challenge—especially when they span across multiple number bases. Imagine trying to find numbers that not only look the same forwards and backwards in base-10, but also in base-k. That’s the crux of the k-mirror number challenge.

Let’s dive into the formal problem definition to see how this works:

🧠 Problem Summary

You're given two integers:

k: the base in which we check for palindromes
n: the number of k-mirror numbers to find

A k-mirror number is a positive integer that:

Is a palindrome in base-10
Is also a palindrome in base-k

Your task: return the sum of the first n such numbers.

🧩 Intuition

This is a palindrome-generation and filtering problem. The challenge lies in generating candidate numbers efficiently and checking their representations in different bases.

Key Observations:

Not every decimal palindrome is a k-palindrome (i.e., palindrome in base-k)
Instead of checking all numbers, generate only palindromes in base-10 (which drastically reduces search space)
For each generated number, convert it to base-k and check if that string is also a palindrome

🪄 Approach

Start from the smallest base-10 palindromes: 1-digit numbers.
Use a helper function to generate the next decimal palindrome.
For each candidate:

Convert it to base-k
Check if that base-k representation is a palindrome
1. If it is, add it to the sum and count
2. Stop when we find n such numbers

💻 C++ Code

class Solution {
public:
    bool isPalindrome(string s) {
        return s == string(s.rbegin(), s.rend());
    }

    string toBaseK(long long num, int k) {
        string res;
        while (num > 0) {
            res += to_string(num % k);
            num /= k;
        }
        reverse(res.begin(), res.end());
        return res;
    }

    long long kMirror(int k, int n) {
        long long sum = 0;
        int len = 1;
        while (n > 0) {
            for (int half = pow(10, (len - 1) / 2); half < pow(10, (len + 1) / 2) && n > 0; ++half) {
                string h = to_string(half);
                string r = h;
                reverse(r.begin(), r.end());
                string full = h + (len % 2 ? r.substr(1) : r);
                long long num = stoll(full);
                if (isPalindrome(toBaseK(num, k))) {
                    sum += num;
                    --n;
                }
            }
            ++len;
        }
        return sum;
    }
};

💻 JavaScript Code

function isPalindrome(s) {
    return s === s.split('').reverse().join('');
}

function toBaseK(num, k) {
    return num.toString(k);
}

var kMirror = function(k, n) {
    let sum = 0;
    let len = 1;
    while (n > 0) {
        let lower = Math.pow(10, Math.floor((len - 1) / 2));
        let upper = Math.pow(10, Math.ceil((len) / 2));
        for (let half = lower; half < upper && n > 0; half++) {
            let h = String(half);
            let r = h.split('').reverse().join('');
            let full = h + (len % 2 ? r.slice(1) : r);
            let num = parseInt(full);
            if (isPalindrome(toBaseK(num, k))) {
                sum += num;
                n--;
            }
        }
        len++;
    }
    return sum;
};

🐍 Python Code

class Solution:
    def kMirror(self, k: int, n: int) -> int:
        def is_palindrome(s):
            return s == s[::-1]

        def to_base_k(num, k):
            res = ""
            while num:
                res = str(num % k) + res
                num //= k
            return res

        def generate_palindromes():
            length = 1
            while True:
                for half in range(10 ** ((length - 1) // 2), 10 ** ((length + 1) // 2)):
                    s = str(half)
                    yield int(s + s[-2::-1] if length % 2 else s + s[::-1])
                length += 1

        ans = 0
        count = 0
        for num in generate_palindromes():
            if is_palindrome(to_base_k(num, k)):
                ans += num
                count += 1
                if count == n:
                    break
        return ans