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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of k-Mirror Numbers

Number: 2202

Difficulty: Hard

Paid? No

Companies: Cisco

Problem Description

Given a base k and an integer n, find the sum of the n smallest k-mirror numbers. A k-mirror number is a positive integer (without leading zeros) which is palindromic in base-10 and whose representation in base-k is also palindromic.

Key Insights

  • k-mirror numbers must be palindromic in both base-10 and base-k.
  • In base-10, palindromic numbers can be generated by constructing half of the number and then mirroring it.
  • Only a small subset of base-10 palindromes (often starting from single digit numbers) will also be palindromic when converted to base-k.
  • Since n is small (n ≤ 30), we can generate palindromes sequentially by increasing the number of digits until we have found n valid numbers.
  • The helper function to convert a number to a string in base-k and check if it reads the same forwards and backwards is crucial.

Space and Time Complexity

Time Complexity: O(X * D) where X is the number of generated candidate palindromes (which is small given n ≤ 30) and D is the number of digits used in conversion and palindrome checks. Space Complexity: O(1) additional space besides the space needed to store the few candidate numbers.

Solution

We generate base-10 palindromic numbers in increasing order. For each candidate:

  1. Convert the candidate number to base-k.
  2. Check if the base-k string is a palindrome.
  3. If both checks pass, add the candidate to the result list.
  4. Continue until we have found n valid k-mirror numbers, then return their sum.

The key data structures include:

  • Looping constructs to generate palindromes by constructing the left half and mirroring it.
  • Helper functions to perform base conversion and palindrome check.

The approach takes advantage of the fact that n is small, allowing us to generate candidates by digit-length until enough numbers are found without needing to optimize for extremely large numbers.

Code Solutions

# Python solution with line-by-line comments
def is_palindrome(s):
    # Check if the string s is a palindrome.
    return s == s[::-1]

def convert_to_base(num, base):
    # Convert a number to its string representation in the given base.
    digits = []
    while num:
        digits.append(str(num % base))
        num //= base
    return ''.join(reversed(digits)) if digits else "0"

def generate_palindromes(length):
    # Generate palindromes of a given digit length in base-10.
    pal_list = []
    half_len = (length + 1) // 2   # half length used to construct the palindrome
    start = 10**(half_len - 1)
    end = 10**half_len
    for half in range(start, end):
        half_str = str(half)
        # If the length is odd, exclude the last digit for mirroring.
        if length % 2 == 0:
            pal_str = half_str + half_str[::-1]
        else:
            pal_str = half_str + half_str[-2::-1]
        pal_list.append(int(pal_str))
    return pal_list

def kMirror(k, n):
    count = 0
    total_sum = 0
    length = 1
    # Keep generating palindromes of increasing digit lengths until we have n valid numbers.
    while count < n:
        for pal in generate_palindromes(length):
            # Convert the candidate palindrome to base-k.
            base_k_repr = convert_to_base(pal, k)
            # If its base-k representation is also a palindrome, add it.
            if is_palindrome(base_k_repr):
                total_sum += pal
                count += 1
                # When we've reached n valid numbers, return the sum.
                if count == n:
                    return total_sum
        length += 1

# Example usage:
# k = 2, n = 5 should return 25.
print(kMirror(2, 5))
← Back to All Questions