Question

2081. Sum of k-Mirror Numbers

中文文档

Description

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

Solutions

Solution 1

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;
  }
}