We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of k-Mirror Numbers

Difficulty: Hard

Problem 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. Given the base k and the number n, return the sum of the n smallest k-mirror numbers.

Key Insights

  • A number must be palindromic in both base-10 and base-k to qualify as a k-mirror number.
  • To find k-mirror numbers, we can generate palindromic numbers in base-10 and check their representations in base-k.
  • The search can be restricted to odd and even length palindromes separately, as they can generate different sets of numbers.

Space and Time Complexity

Time Complexity: O(n * m * log(m)), where n is the number of k-mirror numbers needed, and m is the maximum number checked for palindromicity.
Space Complexity: O(n), primarily for storing the k-mirror numbers found.

Solution

To solve the problem, we will:

  1. Generate palindromic numbers in base-10.
  2. For each palindromic number, convert it to base-k and check if it is also palindromic.
  3. Keep track of the count of k-mirror numbers found until we reach n.
  4. Sum the valid k-mirror numbers and return the result.

The primary data structure used here is a list to store the k-mirror numbers, and we utilize string manipulation for checking palindromic properties.

Code Solutions

def is_palindrome(s):
    return s == s[::-1]

def to_base_k(num, k):
    if num == 0:
        return "0"
    digits = []
    while num:
        digits.append(int(num % k))
        num //= k
    return ''.join(str(x) for x in digits[::-1])

def k_mirror(k, n):
    count = 0
    total_sum = 0
    num = 1
    
    while count < n:
        if is_palindrome(str(num)):
            base_k_repr = to_base_k(num, k)
            if is_palindrome(base_k_repr):
                total_sum += num
                count += 1
        num += 1
    
    return total_sum
← Back to All Questions