# Sum of k-Mirror Numbers
**Difficulty:** HARD
[External](https://leetcode.com/problems/sum-of-k-mirror-numbers)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-k-mirror-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco)
---
## 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_.

**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`

# Approaches
## Brute-Force Iteration
The most straightforward method is to iterate through all positive integers, one by one. For each integer, we check if it satisfies the two conditions: being a palindrome in base-10 and being a palindrome in base-k. We continue this process until we have found `n` such numbers and then sum them up.
**Time:** Let `M` be the `n`-th k-mirror number. The algorithm iterates up to `M`. For each number `i` from 1 to `M`, it performs two palindrome checks. The checks take `O(log10(i))` and `O(log_k(i))` time, respectively. The total time complexity is approximately `O(M * log M)`. · **Space:** O(log M), where `M` is the `n`-th k-mirror number. This space is used to store the string representations of the numbers during the palindrome checks.
**Pros:** Simple to understand and implement.; Correctness is easy to verify.
**Cons:** Highly inefficient and can be very slow. The `n`-th k-mirror number can be very large, leading to a huge number of iterations.; Checks many numbers that are not even base-10 palindromes, wasting a lot of computation.
### Explanation
This approach involves a simple loop that starts from 1 and increments. In each iteration, the current number is tested. To test if a number is a k-mirror number, we need two helper functions: one to check for palindromes in base-10 and another for base-k. A number is converted to its string representation in the respective base, and then the string is checked for the palindrome property. We keep a count of the k-mirror numbers found and stop once we reach `n`.

```java
class Solution {
    public long kMirror(int k, int n) {
        long sum = 0;
        int count = 0;
        long num = 1;
        
        while (count < n) {
            if (isBase10Palindrome(num) && isBaseKPalindrome(num, k)) {
                sum += num;
                count++;
            }
            num++;
        }
        return sum;
    }

    private boolean isBase10Palindrome(long num) {
        String s = Long.toString(num);
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    private boolean isBaseKPalindrome(long num, int k) {
        String s = Long.toString(num, k);
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Initialize `sum = 0`, `count = 0`, and `num = 1`.
- Loop while `count < n`:
  - Check if `num` is a palindrome in base-10.
  - If it is, check if `num` is a palindrome in base-k.
  - If both are true, add `num` to `sum` and increment `count`.
  - Increment `num`.
- Return `sum`.

## Generate Base-10 Palindromes and Check
A significant improvement over brute force is to only check numbers that are already palindromic in base-10. We can generate base-10 palindromes in increasing order and, for each, check if its base-k representation is also a palindrome. This avoids checking a vast majority of numbers that couldn't possibly be k-mirror numbers.
**Time:** Let `M` be the `n`-th k-mirror number. The number of base-10 palindromes up to `M` is approximately `2 * sqrt(M)`. For each palindrome, we perform a base-k conversion and palindrome check, which takes `O(log_k(M))` time. The total time complexity is roughly `O(sqrt(M) * log_k(M))`. · **Space:** O(log M), where `M` is the `n`-th k-mirror number. This space is for storing string representations of the numbers.
**Pros:** Much faster than the brute-force approach by drastically reducing the number of candidates.; Generates candidates in increasing order of value, which simplifies finding the `n` smallest ones.
**Cons:** Less efficient than generating base-k palindromes. For a small `k`, base-10 palindromes are much more numerous than base-k palindromes of similar magnitude, so this approach still checks more candidates than necessary.
### Explanation
Instead of checking every integer, we can generate only the numbers that are palindromes in base-10. Base-10 palindromes can be constructed from a "first half". For example, from the number 12, we can construct two palindromes: 1221 (even length) and 121 (odd length). We can generate these first halves (`i = 1, 2, 3, ...`) and from them construct the full palindromes. This ensures we generate them in increasing order. For each generated base-10 palindrome, we convert it to its base-k string representation and check if that is also a palindrome.

```java
class Solution {
    public long kMirror(int k, int n) {
        long sum = 0;
        int count = 0;
        
        for (int len = 1; ; len++) {
            int halfLen = (len + 1) / 2;
            long start = (long) Math.pow(10, halfLen - 1);
            long end = (long) Math.pow(10, halfLen);
            
            for (long i = start; i < end; i++) {
                String firstHalf = Long.toString(i);
                StringBuilder secondHalf = new StringBuilder(firstHalf).reverse();
                
                String palindromeStr;
                if (len % 2 == 1) {
                    palindromeStr = firstHalf + secondHalf.substring(1);
                } else {
                    palindromeStr = firstHalf + secondHalf.toString();
                }
                
                long num = Long.parseLong(palindromeStr);
                
                if (isBaseKPalindrome(num, k)) {
                    sum += num;
                    count++;
                    if (count == n) {
                        return sum;
                    }
                }
            }
        }
    }

    private boolean isBaseKPalindrome(long num, int k) {
        String s = Long.toString(num, k);
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Initialize `sum = 0` and `count = 0`.
- Loop through potential palindrome lengths `len = 1, 2, 3, ...`.
- For each `len`, determine the length of the first half: `halfLen = (len + 1) / 2`.
- Iterate through all possible first halves `i` (as numbers from `10^(halfLen-1)` to `10^halfLen - 1`).
- For each `i`, get its string representation `s_half`.
- Construct the full base-10 palindrome string `p` from `s_half`.
- Convert `p` to a number `num`.
- Check if `num` is a palindrome in base-k.
- If it is, add `num` to `sum` and increment `count`.
- Stop when `count` reaches `n` and return `sum`.

## Generate Base-k Palindromes and Check
This approach leverages the small size of the base `k` (k <= 9). Instead of iterating through all numbers or all base-10 palindromes, we generate palindromic numbers in base `k` directly. Since `k` is small, these numbers are much sparser than base-10 palindromes. Each generated base-k palindrome is then converted to base-10 and checked if it's a palindrome. This significantly reduces the number of candidates to test, leading to a highly efficient solution.
**Time:** The complexity depends on the magnitude of the `n`-th k-mirror number, `M_n`. We generate base-k palindromes. The number of base-k palindromes of length up to `L = log_k(M_n)` is roughly `k * k^(L/2)`, which is proportional to `sqrt(M_n)`. For each candidate, conversion and checking takes `O(log M_n)` time. The performance is excellent for the given constraints because the number of candidates is very small. · **Space:** O(log_k M_n), where `M_n` is the `n`-th k-mirror number. This space is used to store the string representations of the numbers in base-10 and base-k.
**Pros:** Highly efficient due to a much smaller search space (base-k palindromes), especially since `k` is small.; Directly generates candidates that satisfy one of the two palindrome conditions, minimizing wasted checks.
**Cons:** The logic for generating palindromes in a specific base can be slightly more complex to implement than simple iteration.; The generated numbers are not strictly in increasing order of their base-10 value (e.g., a number with a longer base-k representation can be smaller than one with a shorter representation), but grouping by length of the base-k representation keeps them manageable and finds them in a generally increasing order.
### Explanation
The core idea is to flip the problem: generate numbers that satisfy the base-k palindrome property and then test the base-10 property. We can generate base-k palindromes systematically by their length. For a given length `len`, we can construct all palindromes by generating their first half (of length `(len+1)/2`). The first half is a number whose base-k representation has `halfLen` digits. We can iterate through these first halves, construct the full base-k palindrome string, convert it to its base-10 value, and then check if this value is a base-10 palindrome.

```java
class Solution {
    public long kMirror(int k, int n) {
        long sum = 0;
        int count = 0;
        
        for (int len = 1; ; len++) {
            int halfLen = (len + 1) / 2;
            long start = (long) Math.pow(k, halfLen - 1);
            long end = (long) Math.pow(k, halfLen);
            
            for (long i = start; i < end; i++) {
                String firstHalf = Long.toString(i, k);
                StringBuilder secondHalf = new StringBuilder(firstHalf).reverse();
                String palindromeInBaseK;
                if (len % 2 == 1) {
                    palindromeInBaseK = firstHalf + secondHalf.substring(1);
                } else {
                    palindromeInBaseK = firstHalf + secondHalf.toString();
                }
                
                long num = Long.parseLong(palindromeInBaseK, k);
                
                if (isBase10Palindrome(num)) {
                    sum += num;
                    count++;
                    if (count == n) {
                        return sum;
                    }
                }
            }
        }
    }

    private boolean isBase10Palindrome(long num) {
        String s = Long.toString(num);
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
```
### Algorithm
- Initialize `sum = 0` and `count = 0`.
- Loop through the length of the base-k representation, `len = 1, 2, 3, ...`.
- For each `len`, determine the length of the first half: `halfLen = (len + 1) / 2`.
- Iterate through all possible first halves (as numbers from `k^(halfLen-1)` to `k^halfLen - 1`).
- For each first half `i`, convert it to a base-k string `s_half`.
- Construct the full base-k palindrome string `p_k` from `s_half`.
- Convert `p_k` to its base-10 value `num`.
- Check if `num` is a base-10 palindrome.
- If yes, add `num` to `sum` and increment `count`.
- If `count` reaches `n`, break all loops and return `sum`.

# Solutions
### Java

```java
class Solution {
public
  long kMirror(int k, int n) {
    long ans = 0;
    for (int l = 1;; ++l) {
      int x = (int)Math.pow(10, (l - 1) / 2);
      int y = (int)Math.pow(10, (l + 1) / 2);
      for (int i = x; i < y; i++) {
        long v = i;
        for (int j = l % 2 == 0 ? i : i / 10; j > 0; j /= 10) {
          v = v * 10 + j % 10;
        }
        String ss = Long.toString(v, k);
        if (check(ss.toCharArray())) {
          ans += v;
          if (--n == 0) {
            return ans;
          }
        }
      }
    }
  }
private
  boolean check(char[] c) {
    for (int i = 0, j = c.length - 1; i < j; i++, j--) {
      if (c[i] != c[j]) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long kMirror(int k, int n) {
    long long ans = 0;
    for (int l = 1;; ++l) {
      int x = pow(10, (l - 1) / 2);
      int y = pow(10, (l + 1) / 2);
      for (int i = x; i < y; ++i) {
        long long v = i;
        int j = (l % 2 == 0) ? i : i / 10;
        while (j > 0) {
          v = v * 10 + j % 10;
          j /= 10;
        }
        if (check(v, k)) {
          ans += v;
          if (--n == 0) {
            return ans;
          }
        }
      }
    }
  }

private:
  bool check(long long x, int k) {
    vector<int> s;
    while (x > 0) {
      s.push_back(x % k);
      x /= k;
    }
    for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
      if (s[i] != s[j]) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def kMirror(self, k: int, n: int) -> int: def check(x: int, k: int) -> bool: s = [] while x: s . append(x % k) x //= k return s == s[:: - 1] ans = 0 for l in count(1): x = 10 ** ((l - 1) // 2) y = 10 ** ((l + 1) // 2) for i in range(x, y): v = i j = i if l % 2 == 0 else i // 10 while j > 0: v = v * 10 + j % 10 j //= 10 if check(v, k): ans += v n -= 1 if n == 0: return ans

```