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: Enumeration

• Time complexity: O(nlogₖ(10^18))
• Space complexity: O(logₖ(10^18))

 

JavaScript

/**
 * @param {number} k
 * @param {number} n
 * @return {number}
 */
const kMirror = function (k, n) {
  let mirrorNumber = [0];
  let result = 0;

  const nextMirrorNumber = () => {
    const { length } = mirrorNumber;

    for (let index = Math.floor(length / 2); index < length; index++) {
      const nextNum = mirrorNumber[index] + 1;

      if (nextNum >= k) continue;

      mirrorNumber[index] = nextNum;
      mirrorNumber[length - 1 - index] = nextNum;

      for (let left = Math.floor(length / 2); left < index; left++) {
        mirrorNumber[left] = 0;
        mirrorNumber[length - 1 - left] = 0;
      }

      return mirrorNumber;
    }

    const middle = new Array(length - 1).fill(0);

    return [1, ...middle, 1];
  };

  const getValidNumber = () => {
    mirrorNumber = nextMirrorNumber();
    const num = Number.parseInt(mirrorNumber.join(''), k);
    const splitNum = `${num}`.split('');
    let left = 0;
    let right = splitNum.length - 1;

    while (left < right) {
      if (splitNum[left] !== splitNum[right]) {
        return getValidNumber();
      }

      left += 1;
      right -= 1;
    }

    return num;
  };

  for (let count = 1; count <= n; count++) {
    result += getValidNumber();
  }

  return result;
};