Problem Statement

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.

LeetCode:

Sum of k-Mirror Numbers

Constraints:

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

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.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

Since we need the sum of the first n numbers that are palindromes in base-10 and also palindromes in base-k, we can:

1. Start from 1 and check each number.
2. If the number is a palindrome in base-10, check its base-k representation.
3. If its base-k form is also a palindrome, add it to the sum and increment the count.
4. Repeat until we've found n such numbers.

Code:

class Solution {
public:
    // Function to check if a number is a palindrome in base-10 (normal decimal)
    bool isPalindrome(int num) {
        string str = to_string(num);          // Convert the number to string
        int left = 0, right = str.size() - 1; // Two pointers: one at start, one at end

        // Compare characters from both ends towards the center
        while (left <= right) {
            if (str[left++] != str[right--])  // If characters don't match, not a palindrome
                return false;
        }
        return true; // If loop completes, it's a palindrome
    }

    // Function to check if a number is a palindrome in base-k
    bool isBaseKPalindrome(int n, int k) {
        string str = "";

        // Convert number 'n' to base-k representation
        while (n != 0) {
            str += to_string(n % k); // Get last digit in base-k and add to string
            n /= k;                  // Move to next higher digit
        }

        // Now, check if the base-k string is a palindrome
        int left = 0, right = str.size() - 1;
        while (left <= right) {
            if (str[left++] != str[right--])  // If mismatch, not a palindrome
                return false;
        }

        return true; // It's a palindrome in base-k
    }

    // Main function to find the sum of first 'n' k-mirror numbers
    long long kMirror(int k, int n) {
        long long sum = 0; // To store the final sum of k-mirror numbers
        int count = 0;     // To count how many valid numbers we've found
        int num = 1;       // Start checking numbers from 1

        // Keep checking until we find 'n' k-mirror numbers
        while (count < n) {
            // Check if number is palindrome in both base-10 and base-k
            if (isPalindrome(num) && isBaseKPalindrome(num, k)) {
                sum += num;   // Add valid number to the sum
                count++;      // Increment the count of valid numbers found
            }
            num++; // Move to next number
        }

        return sum; // Return the final sum of k-mirror numbers
    }
};

Complexity Analysis:

• Time Complexity:O(M log M)
• Space Complexity:O(log M)

2️⃣ Optimal Approach

💡 Intuition:

A k-mirror number is a number that:

• Is a palindrome in base 10 (like 121, 1331, 12321),
• And also a palindrome in base k (like 101 in base 2 is also a palindrome).

Instead of checking every number from 1 upward, we efficiently generate decimal palindromes only, then:

• Convert each to base k,
• Check if it's a palindrome in that base.

This avoids checking numbers that are not even palindromes in base 10, reducing computation.

Approach:

Step 1: Generate Decimal Palindromes

• A palindrome can be generated by mirroring digits.
• We build all palindromes of length L, starting with L = 1, and gradually increasing.
• A length L palindrome can be created by:
  • Taking a number (like 123),
  • Reversing it (321),
  • Appending to make 123321 (even-length) or 12321 (odd-length).

This gives us all base-10 palindromes of a certain length in order.

Step 2: Convert to Base-k and Check

• For each base-10 palindrome:
  • Convert it to base k using division/modulo.
  • Check if the result is a palindrome.

If both are palindromes → it's a valid k-mirror number, add it to the sum.

Step 3: Continue Until n Found

• Keep a counter and keep generating longer palindromes until n valid numbers are found.
• Return the total sum.

Code:

class Solution {
public:

    // Helper function to check if a given string is a palindrome
    bool isPalindrome(string baseK) {
        int i = 0;
        int j = baseK.length() - 1;

        // Compare characters from both ends towards the center
        while(i <= j) {
            if(baseK[i] != baseK[j]) {
                return false; // Not a palindrome if characters don't match
            }
            i++;
            j--;
        }

        return true; // All characters matched => palindrome
    }

    // Helper function to convert a number from base 10 to base-k as a string
    string convertToBaseK(long long num, int k) {
        if(num == 0) {
            return "0"; // Edge case
        }

        string res = "";
        while(num > 0) {
            res += to_string(num % k); // Add remainder as a character
            num /= k;                  // Divide by base
        }

        // Note: digits are in reverse order but it's okay for palindrome check
        return res;
    }

    // Main function to calculate the sum of first 'n' k-mirror numbers
    long long kMirror(int k, int n) {
        long long sum = 0; // To store the sum of k-mirror numbers
        int L = 1;         // Start checking palindromes of length 1

        // Keep finding k-mirror numbers until we have 'n' of them
        while(n > 0) {
            int half_length = (L + 1) / 2; // Length of the first half of the palindrome

            // Generate all numbers of half_length digits (e.g. 1 to 9, 10 to 99, etc.)
            long long min_num = pow(10, half_length - 1);
            long long max_num = pow(10, half_length) - 1;

            for(int num = min_num; num <= max_num; num++) {
                string first_half = to_string(num);     // Convert number to string
                string second_half = first_half;
                reverse(begin(second_half), end(second_half)); // Reverse for mirroring

                string pal = "";
                if(L % 2 == 0) {
                    // Even length palindrome: just mirror the entire first half
                    pal = first_half + second_half;
                } else {
                    // Odd length palindrome: mirror all but the last digit
                    pal = first_half + second_half.substr(1);
                }

                long long pal_num = stoll(pal); // Convert back to number

                // Convert this decimal palindrome to base-k
                string baseK = convertToBaseK(pal_num, k);

                // Check if it's also a palindrome in base-k
                if(isPalindrome(baseK)) {
                    sum += pal_num; // It's a k-mirror number; add to sum
                    n--;            // One less to find
                    if(n == 0) {
                        break;      // Stop early if we've found enough
                    }
                }
            }

            L++; // Move to next longer length palindromes
        }

        return sum;
    }
};

Complexity Analysis:

• Time Complexity:O(n * L)
  • where L is the number of digits in the largest k-mirror number found.
• Space Complexity:O(L)