Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 <= 30Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
2 5
3 7
7 17
strobogrammatic-number-ii)prime-palindrome)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2081: Sum of k-Mirror Numbers
class Solution {
public long kMirror(int k, int n) {
long ans = 0;
for (int l = 1;; l++) {
int x = (int) Math.pow(10, (l - 1) / 2);
int y = (int) Math.pow(10, (l + 1) / 2);
for (int i = x; i < y; i++) {
long v = i;
int j = (l % 2 == 0) ? i : i / 10;
while (j > 0) {
v = v * 10 + j % 10;
j /= 10;
}
if (check(v, k)) {
ans += v;
n--;
if (n == 0) {
return ans;
}
}
}
}
}
private boolean check(long x, int k) {
List<Integer> s = new ArrayList<>();
while (x > 0) {
s.add((int) (x % k));
x /= k;
}
for (int i = 0, j = s.size() - 1; i < j; ++i, --j) {
if (!s.get(i).equals(s.get(j))) {
return false;
}
}
return true;
}
}
// Accepted solution for LeetCode #2081: Sum of k-Mirror Numbers
func kMirror(k int, n int) int64 {
check := func(x int64, k int) bool {
s := []int{}
for x > 0 {
s = append(s, int(x%int64(k)))
x /= int64(k)
}
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
var ans int64 = 0
for l := 1; ; l++ {
x := pow10((l - 1) / 2)
y := pow10((l + 1) / 2)
for i := x; i < y; i++ {
v := int64(i)
j := i
if l%2 != 0 {
j = i / 10
}
for j > 0 {
v = v*10 + int64(j%10)
j /= 10
}
if check(v, k) {
ans += v
n--
if n == 0 {
return ans
}
}
}
}
}
func pow10(exp int) int {
res := 1
for i := 0; i < exp; i++ {
res *= 10
}
return res
}
# Accepted solution for LeetCode #2081: Sum of k-Mirror Numbers
class Solution:
def kMirror(self, k: int, n: int) -> int:
def check(x: int, k: int) -> bool:
s = []
while x:
s.append(x % k)
x //= k
return s == s[::-1]
ans = 0
for l in count(1):
x = 10 ** ((l - 1) // 2)
y = 10 ** ((l + 1) // 2)
for i in range(x, y):
v = i
j = i if l % 2 == 0 else i // 10
while j > 0:
v = v * 10 + j % 10
j //= 10
if check(v, k):
ans += v
n -= 1
if n == 0:
return ans
// Accepted solution for LeetCode #2081: Sum of k-Mirror Numbers
/**
* [2081] Sum of k-Mirror Numbers
*
* 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
*
*/
pub struct Solution {}
// problem: https://leetcode.com/problems/sum-of-k-mirror-numbers/
// discuss: https://leetcode.com/problems/sum-of-k-mirror-numbers/discuss/?currentPage=1&orderBy=most_votes&query=
// submission codes start here
impl Solution {
pub fn k_mirror(k: i32, n: i32) -> i64 {
0
}
}
// submission codes end
#[cfg(test)]
mod tests {
use super::*;
#[test]
#[ignore]
fn test_2081_example_1() {
let k = 2;
let n = 5;
let result = 25;
assert_eq!(Solution::k_mirror(k, n), result);
}
#[test]
#[ignore]
fn test_2081_example_2() {
let k = 3;
let n = 7;
let result = 499;
assert_eq!(Solution::k_mirror(k, n), result);
}
#[test]
#[ignore]
fn test_2081_example_3() {
let k = 7;
let n = 17;
let result = 20379000;
assert_eq!(Solution::k_mirror(k, n), result);
}
}
// Accepted solution for LeetCode #2081: Sum of k-Mirror Numbers
function kMirror(k: number, n: number): number {
function check(x: number, k: number): boolean {
const s: number[] = [];
while (x > 0) {
s.push(x % k);
x = Math.floor(x / k);
}
for (let i = 0, j = s.length - 1; i < j; i++, j--) {
if (s[i] !== s[j]) {
return false;
}
}
return true;
}
let ans = 0;
for (let l = 1; ; l++) {
const x = Math.pow(10, Math.floor((l - 1) / 2));
const y = Math.pow(10, Math.floor((l + 1) / 2));
for (let i = x; i < y; i++) {
let v = i;
let j = l % 2 === 0 ? i : Math.floor(i / 10);
while (j > 0) {
v = v * 10 + (j % 10);
j = Math.floor(j / 10);
}
if (check(v, k)) {
ans += v;
n--;
if (n === 0) {
return ans;
}
}
}
}
}
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.