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.
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.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 <= 91 <= n <= 30This approach involves a brute-force method where we generate all numbers starting from 1 and check if they are palindromic in both base-10 and base-k. We keep a count until we reach the desired number of k-mirror numbers.
This solution defines functions to check for palindromes and convert numbers to base-k. By iterating through numbers and checking both conditions, we ensure the numbers are k-mirror.
C++
Java
JavaScript
C#
Time Complexity: O(n*m), where n is the number of k-mirror numbers required, and m depends on the number being iterated over. Space Complexity: O(1) for space used in calculations.
This approach optimizes the search by constructing palindromic numbers directly. For each half-length, generate palindromes and convert to base-k to verify the k-mirror condition. This approach eliminates non-palindromes from checks.
In this Python solution, we pre-generate numeric palindromes instead of inspecting each number linearly, thereby enhancing efficiency. By iterating over possible palindromic lengths, we streamline the search space for k-mirror numbers.
C++
Java
JavaScript
C#
Time Complexity: Depending on the implementation details of palindrome generation and validation, it is much less than brute-force for larger n. Space Complexity: Depends on palindromic generation results.
| Approach | Complexity |
|---|---|
| Brute-force Generation | Time Complexity: O(n*m), where n is the number of k-mirror numbers required, and m depends on the number being iterated over. Space Complexity: O(1) for space used in calculations. |
| Palindrome Construction | Time Complexity: Depending on the implementation details of palindrome generation and validation, it is much less than brute-force for larger n. Space Complexity: Depends on palindromic generation results. |
How to EASILY solve LeetCode problems • NeetCode • 427,724 views views
Watch 9 more video solutions →Practice Sum of k-Mirror Numbers with our built-in code editor and test cases.
Practice on FleetCode