2081. Sum of k-Mirror Numbers

HardMathEnumeration

Problem Description

A k-mirror number is a positive integer with no leading zeros that is symmetrical; it reads the same forward and backward. This symmetry must hold true when the number is expressed in both base-10 (our standard numeral system) and base-k (a numeral system with base k). For example, the number 9 is the same whether read forwards or backwards in base-10, and when converted to base-2, it becomes '1001', which is also symmetrical.

However, not every number is k-mirror. For instance, the number 4 in base-10 becomes '100' in base-2. Since '100' isn't symmetrical, 4 is not a 2-mirror number.

The problem asks us to calculate the sum of the n smallest k-mirror numbers. In other words, we must find the first n numbers that are k-mirror numbers and add them together.

Intuition

The solution approach for finding k-mirror numbers involves generating potential mirror numbers in base-10 and then checking if they are also symmetrical in base-k. Instead of generating all numbers and checking each one, a more efficient approach is to generate numbers that are already palindromic in base-10. If a number is a palindrome in base-10, there's no need to check it for symmetry in this base.

To generate palindromes in base-10, we start by considering numbers of increasing lengths. For each length, we form the first half of a potential palindrome and then mirror it to create the second half, ensuring the entire number is symmetrical in base-10.

For example, if our first half is '123', the whole palindrome can be '12321' for odd lengths, and '123321' for even lengths. Note that we have to generate both even and odd length palindromes because they may both yield valid k-mirror numbers.

Once we create a base-10 palindrome, we convert it to base-k and then check if the base-k representation is also a palindrome. The check is straightforward: compare the first half of the array of characters to the second half and confirm they are identical.

The provided Java function `kMirror(int k, int n)` initializes the answer to 0. It then enters a loop that continues until we find n k-mirror numbers. Inside the loop, we generate base-10 palindromes of increasing length using the loop variable `l`. We use the just-generated palindrome as a long integer `v`, convert `v` to a string in base-k, and then use the `check` helper method to determine if it is also a palindrome in base-k.

Each time we find a k-mirror number, we add it to the `ans` variable and decrement `n`. Once we've found n k-mirror numbers, we return the total sum `ans`.

This approach is efficient because it sidesteps the need to check each base-10 number for palindromic propertiesโwe create only numbers that are already palindromes in base-10. Then we only need to check for palindromic structure in base-k, significantly reducing the number of checks needed.

Solution Approach

The solution uses a mathematical approach to generate palindromes and a brute-force check to determine if those palindromes are k-mirror numbers. Let's break down the implementation into its main components:

1. Palindrome Generation: The outer loop, indicated by `for (int l = 1;; ++l)`, controls the length `l` of the palindromes being generated. The `l` increases after each full iteration, allowing us to create larger palindromes. For half the length (rounded down), we use `int x = (int) Math.pow(10, (l - 1) / 2)`, and for half the length (rounded up), we use `int y = (int) Math.pow(10, (l + 1) / 2)`.

2. Base-10 Palindrome Construction: Inside the loop, `for (int i = x; i < y; i++)` iterates through potential first halves of the palindromic numbers. The variable `v` is then used to construct the full palindrome by appending the reverse of `i`, either including the last digit `(l % 2 == 0 ? i : i / 10)` for even lengths or excluding it for odd lengths.

3. Base-k Conversion: After creating a base-10 palindrome (`v`), we convert it to a string in the base-k numeral system with `String ss = Long.toString(v, k)`.

4. Palindrome Check in Base-k: The private helper function `check(char[] c)` takes in the char array of the base-k representation and uses two pointers (`i` and `j`) to check from both ends towards the center, ensuring that the string is the same forwards and backwards.

5. Summation and Counting: When a k-mirror number is found (i.e., it passes the palindrome check in base-k), it is added to the running total `ans`, and `n` is decremented. We continue generating palindromes and checking for k-mirror symmetry until `n` reaches zeroโat which point we return the sum `ans`.

The algorithm demonstrates efficient use of mathematical properties to limit the search space only to valid palindromes, rather than iterating through all integers. By constructing palindromes of increasing length, we also ensure we are considering the smallest k-mirror numbers in ascending order, which fits the requirement of the problem. The combination of mathematical pattern recognition and brute-force checking results in a direct and effective solution to the problem.

๐ช
Level Up Your
Algo Skills

Example Walkthrough

Let's use `k = 2` and `n = 3` to illustrate the solution approach to finding the sum of the `n` smallest `k`-mirror numbers. We are looking for the sum of the first 3 numbers that are both palindromes in base-10 and base-2.

1. Palindrome Generation in Base-10: Our outer loop constructs base-10 palindromes of increasing length. We begin with the length `l = 1`. This means for half the length (rounded down) `x=1` and half the length (rounded up) `y=10`.

2. Base-10 Palindrome Construction: Inside the loop, we iterate from `x` (in this case, 1) to `y` (less than 10) to create the first half of the palindrome. For `i = 1`, we get `v = 1`, because this is a length one (odd-length) palindrome `i` itself. For an even-length palindrome when `l = 2`, which is not applicable yet, we would mirror the whole digit(s).

3. Base-k Conversion: Now, we convert `v` to base-k (base-2). The number `1` in base-2 is '1', which is still a palindrome.

4. Palindrome Check in Base-k: For our number `1` in base-2, it's clearly symmetrical, so no need to check further.

5. Summation and Counting: Since `1` is a k-mirror number, we add it to the running total `ans = 1` and decrement `n` to 2. We now need to find two more k-mirror numbers.

Next, for `i = 2`, repeating the steps above, we:

1. Create the base-10 palindrome, which is still `2` since it's a single digit.
2. Convert `2` into base-2, which is '10', and this is not a palindrome. Hence, we skip it.

For `i = 3`, we:

1. Have `v = 3`, already a palindrome in base-10.
2. Convert `3` into base-2, which gives us '11'. It is a palindrome in base-2.
3. Since '11' passes the symmetry check, we add 3 to `ans`, resulting in `ans = 4`, and decrement `n` to 1.

For `l` greater than 1, let's say `l = 2`, our process works as follows:

1. Generate potential base-10 palindromes by considering `i` from 1 to 9 (the upper limit `y` here would be 10).
2. For `i = 1`, our even base-10 palindrome construction would yield `11`.
3. Convert `11` into base-2, which gives us '1011', and this is not symmetrical.
4. Thus, `11` in base-10 is not added to `ans` and won't decrement `n`.

This process repeats, increasing `l` as needed, until we find 3 k-mirror numbers in base-10 and base-2. Once we find the required amount, we return the total sum `ans`, which would be the sum of the first three smallest 2-mirror numbers.

The efficiency of this algorithm comes from the fact that rather than brute-forcing through consecutive integers, it constructs potential palindromes and then checks if those palindromes are symmetrical in another base, significantly narrowing the search space.

Python Solution

``````1class Solution:
2
3    def k_mirror(self, base: int, count: int) -> int:
4        sum_of_k_mirrors = 0  # Initialize sum of k-mirror numbers.
5
6        # Loops indefinitely until 'count' k-mirror numbers are found.
7        length = 1
8        while True:
9            # Determine the start and end range for constructing palindrome halves based on the length.
10            start = 10 ** ((length - 1) // 2)
11            end = 10 ** ((length + 1) // 2)
12
13            # Generate all possible palindrome numbers with current length.
14            for i in range(start, end):
15                # Construct the first half of the palindrome number.
16                palindrome = i
17
18                # Generate the second half of the palindrome number.
19                # If the length is even, include the middle digit; if it's odd, exclude it.
20                j = i if length % 2 == 0 else i // 10
21                while j > 0:
22                    palindrome = palindrome * 10 + j % 10  # Append digits in reverse order.
23                    j //= 10
24
25                # Convert the palindrome to its representation in the given base.
26                base_representation = self.to_base(palindrome, base)
27
28                # Check if the base representation is a palindrome.
29                if self.is_palindrome(base_representation):
30                    sum_of_k_mirrors += palindrome  # Add the k-mirror number to the sum.
31                    count -= 1  # Decrement the count of k-mirrors we still need to find.
32                    if count == 0:  # Check if we've found the required number of k-mirror numbers.
33                        return sum_of_k_mirrors  # Return the sum if we have.
34
35            length += 1  # Increment length for the next iteration to generate larger palindromes.
36
37    def to_base(self, num: int, base: int) -> str:
38        # Convert an integer 'num' into a string representation of 'base'.
39        chars = []
40        while num > 0:
41            chars.append(str(num % base))
42            num //= base
43        # Since we build the base representation in reverse, we need to reverse it at the end.
44        return ''.join(reversed(chars))
45
46    def is_palindrome(self, s: str) -> bool:
47        # Check if a string 's' is a palindrome.
48        return s == s[::-1]  # This uses Python's string slicing to reverse the string.
49``````

Java Solution

``````1class Solution {
2
3    // This method returns the sum of the first n k-mirror numbers.
4    public long kMirror(int base, int count) {
5        long sum = 0; // Initialize sum of k-mirror numbers
6
7        // Loops indefinitely until 'count' number of k-mirror numbers are found
8        for (int length = 1; ; ++length) {
9            // Find the start and end range based on the half-length to construct palindrome prefixes
10            int start = (int) Math.pow(10, (length - 1) / 2);
11            int end = (int) Math.pow(10, (length + 1) / 2);
12
13            // Loop to generate all palindrome numbers of the current length
14            for (int i = start; i < end; i++) {
15                long palindrome = i;
16
17                // Construct the second half of the palindrome number based on the length's parity
18                for (int j = length % 2 == 0 ? i : i / 10; j > 0; j /= 10) {
19                    palindrome = palindrome * 10 + j % 10; // Append digits in reverse order to form the palindrome
20                }
21
22                // Convert palindrome to its representation in the given base
23                String baseRepresentation = Long.toString(palindrome, base);
24
25                // Check if the base representation is a palindrome
26                if (isPalindrome(baseRepresentation.toCharArray())) {
27                    sum += palindrome; // Add current palindrome to sum
28                    if (--count == 0) { // Decrement count and check if 'n' k-mirror numbers are found
29                        return sum; // Return the sum if 'n' k-mirror numbers are found
30                    }
31                }
32            }
33        }
34    }
35
36    // This method checks if the character array forms a palindrome
37    private boolean isPalindrome(char[] charArray) {
38        // Compare characters from opposite ends moving towards the center
39        for (int i = 0, j = charArray.length - 1; i < j; i++, j--) {
40            if (charArray[i] != charArray[j]) {
41                return false; // Return false if mismatch is found
42            }
43        }
44        return true; // Return true if the entire array is a palindrome
45    }
46}
47``````

C++ Solution

``````1#include <cmath>
2#include <string>
3#include <vector>
4
5class Solution {
6public:
7    // This method returns the sum of the first 'count' k-mirror numbers in the given 'base'.
8    long long kMirror(int base, int count) {
9        long long sum = 0; // Initialize sum of k-mirror numbers
10
11        // Loops indefinitely until 'count' k-mirror numbers are found
12        for (int length = 1; count > 0; ++length) {
13            // Find the start and end range based on the half-length to construct palindrome prefixes
14            int start = static_cast<int>(std::pow(10, (length - 1) / 2));
15            int end = static_cast<int>(std::pow(10, (length + 1) / 2));
16
17            // Loop to generate all palindrome numbers of the current length
18            for (int i = start; i < end; i++) {
19                long long palindrome = i;
20
21                // Construct the second half of the palindrome number based on the length's parity
22                for (int j = (length % 2 == 0) ? i : i / 10; j > 0; j /= 10) {
23                    palindrome = palindrome * 10 + j % 10; // Append digits in reverse order to form the palindrome
24                }
25
26                // Convert palindrome to its representation in the given base
27                std::string baseRepresentation = toBase(palindrome, base);
28
29                // Check if the base representation is a palindrome
30                if (isPalindrome(baseRepresentation)) {
31                    sum += palindrome; // Add current palindrome to sum
32                    --count; // Decrement count as one k-mirror number was found
33                    if (count == 0) { // If 'count' k-mirror numbers have been found
34                        return sum; // Return the sum of all k-mirror numbers found
35                    }
36                }
37            }
38        }
39    }
40
41private:
42    // This method converts a 'number' into a string representing its value in 'base'.
43    std::string toBase(long long number, int base) {
44        std::string representation;
45        while (number > 0) {
46            int digit = number % base;
47            representation = static_cast<char>(digit < 10 ? '0' + digit : 'A' + (digit - 10)) + representation;
48            number /= base;
49        }
50        return representation.empty() ? "0" : representation;
51    }
52
53    // This method checks if the string 's' forms a palindrome.
54    bool isPalindrome(const std::string& s) {
55        // Compare characters from opposite ends moving towards the center
56        int i = 0, j = s.size() - 1;
57        while (i < j) {
58            if (s[i++] != s[j--]) {
59                return false; // Return false if mismatch is found
60            }
61        }
62        return true; // Return true if the entire string is a palindrome
63    }
64};
65``````

Typescript Solution

``````1// Initialize sum of k-mirror numbers
2let sum: number = 0;
3
4// This function returns the sum of the first 'count' k-mirror numbers in the given 'base'.
5function kMirror(base: number, count: number): number {
6    // Loops indefinitely until 'count' number of k-mirror numbers are found
7    for (let length = 1; ; ++length) {
8        // Find the start and end range based on the half-length to construct palindrome prefixes
9        const start: number = Math.pow(10, Math.floor((length - 1) / 2));
10        const end: number = Math.pow(10, Math.floor((length + 1) / 2));
11
12        // Loop to generate all palindrome numbers of the current length
13        for (let i = start; i < end; i++) {
14            let palindrome: number = i;
15
16            // Construct the second half of the palindrome number based on the length's parity
17            for (let j = length % 2 === 0 ? i : Math.floor(i / 10); j > 0; j = Math.floor(j / 10)) {
18                palindrome = palindrome * 10 + j % 10; // Append digits in reverse order to form the palindrome
19            }
20
21            // Convert palindrome to its representation in the given base
22            const baseRepresentation: string = palindrome.toString(base);
23
24            // Check if the base representation is a palindrome
25            if (isPalindrome(baseRepresentation)) {
26                sum += palindrome; // Add current palindrome to sum
27                if (--count === 0) { // Decrement count and check if 'count' k-mirror numbers are found
28                    return sum; // Return the sum if 'count' k-mirror numbers are found
29                }
30            }
31        }
32    }
33}
34
35// This function checks if the given string is a palindrome
36function isPalindrome(str: string): boolean {
37    // Compare characters from opposite ends moving towards the center
38    for (let i = 0, j = str.length - 1; i < j; i++, j--) {
39        if (str[i] !== str[j]) {
40            return false; // Return false if mismatch is found
41        }
42    }
43    return true; // Return true if the entire string is a palindrome
44}
45``````

Time and Space Complexity

Time Complexity

The time complexity of the given code can be broken down as follows:

1. The outermost loop runs indefinitely (`for (int l = 1;; ++l)`), incrementing `l` until `n` palindromes are found. The value `l` determines the length of the palindrome to be constructed.

2. Inside the outermost `for` loop, calculations to set the bounds `x` and `y` are done using `Math.pow(10, (l - 1) / 2)` and `Math.pow(10, (l + 1) / 2)`, which has a constant time complexity of `O(1)` as it is executed once per loop iteration.

3. The next `for` loop (`for (int i = x; i < y; i++)`) iterates from `x` to `y`. The number of iterations depends on `l` and is approximately `O(10^(l/2))`.

4. Inside this loop, the palindrome is constructed by appending the reverse of the number to itself or its prefix depending on whether `l` is even or odd. This operation has a time complexity of `O(l)` per iteration since reversing a number's digits is linear with the number of digits.

5. The palindrome is then converted to its base-`k` representation (`Long.toString(v, k)`). The conversion's time complexity is `O((log(v)/log(k)) * log(v))`, where `(log(v)/log(k))` is the length of the string in base-`k`.

6. The `check` function, which ensures the base-`k` string is a palindrome, has a time complexity of `O(log(v)/log(k))`.

Considering that `v` grows exponentially with `l`, the dominant factor here is the construction and checking of base-`k` palindromes which happen (10^{l/2}) times for each length `l`. Thus, the total time complexity approximately can be expressed as:

`O(n * l * (log(v)/log(k)) * log(v))`, as this represents the work done to find each of the `n` palindromes.

Given that `n` is the number of palindromes required and `l` increases incrementally, this expression accounts for the increasing cost of producing and checking each palindrome as their lengths increase.

Space Complexity

The space complexity of the code can be analyzed as follows:

1. The variable `v` and the string `ss` carry the largest values in this code. Since these are reused for each palindrome, they do not increase in space usage proportional to the input size.

2. The `check` function uses a few variables for iteration, which does not significantly contribute to the space complexity.

3. No additional arrays or data structures are used that grow with input size.

Thus, the space complexity is primarily driven by the call stack for each recursive call used in number conversion and checking, which yields:

• `O(l)` for the recursion in creating the palindrome.
• `O(log(v))` for space required for base-`k` conversion.

Since `l` is linearly related to `log(v)` (as the palindrome `v` will have a length corresponding to `l`), the space complexity is approximately `O(log(v))`. However, because `log(v)` is a constant relative to `v` itself and does not grow with the input size `n`, the overall space complexity of the code is `O(1)`, i.e., constant space complexity assuming that `k` is also constant.

๐
Become an
Algo Monster

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ
โTA ๐จโ๐ซ