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.
Nearly everyone has used the Multiplication Table. The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed).
Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table.
Example 1:
Input: m = 3, n = 3, k = 5 Output: 3 Explanation: The 5th smallest number is 3.
Example 2:
Input: m = 2, n = 3, k = 6 Output: 6 Explanation: The 6th smallest number is 6.
Constraints:
1 <= m, n <= 3 * 1041 <= k <= m * nProblem summary: Nearly everyone has used the Multiplication Table. The multiplication table of size m x n is an integer matrix mat where mat[i][j] == i * j (1-indexed). Given three integers m, n, and k, return the kth smallest element in the m x n multiplication table.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Binary Search
3 3 5
2 3 6
kth-smallest-element-in-a-sorted-matrix)find-k-th-smallest-pair-distance)k-th-smallest-prime-fraction)minimum-time-to-eat-all-grains)kth-smallest-amount-with-single-denomination-combination)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #668: Kth Smallest Number in Multiplication Table
class Solution {
public int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n;
while (left < right) {
int mid = (left + right) >>> 1;
int cnt = 0;
for (int i = 1; i <= m; ++i) {
cnt += Math.min(mid / i, n);
}
if (cnt >= k) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
// Accepted solution for LeetCode #668: Kth Smallest Number in Multiplication Table
func findKthNumber(m int, n int, k int) int {
left, right := 1, m*n
for left < right {
mid := (left + right) >> 1
cnt := 0
for i := 1; i <= m; i++ {
cnt += min(mid/i, n)
}
if cnt >= k {
right = mid
} else {
left = mid + 1
}
}
return left
}
# Accepted solution for LeetCode #668: Kth Smallest Number in Multiplication Table
class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
left, right = 1, m * n
while left < right:
mid = (left + right) >> 1
cnt = 0
for i in range(1, m + 1):
cnt += min(mid // i, n)
if cnt >= k:
right = mid
else:
left = mid + 1
return left
// Accepted solution for LeetCode #668: Kth Smallest Number in Multiplication Table
struct Solution;
impl Solution {
fn find_kth_number(m: i32, n: i32, k: i32) -> i32 {
let mut lo = 1;
let mut hi = m * n;
while lo < hi {
let mi = lo + (hi - lo) / 2;
if Self::count(mi, m, n) < k {
lo = mi + 1;
} else {
hi = mi;
}
}
lo
}
fn count(x: i32, m: i32, n: i32) -> i32 {
let mut res = 0;
for i in 1..=m {
res += n.min(x / i);
}
res
}
}
#[test]
fn test() {
let m = 3;
let n = 3;
let k = 5;
let res = 3;
assert_eq!(Solution::find_kth_number(m, n, k), res);
}
// Accepted solution for LeetCode #668: Kth Smallest Number in Multiplication Table
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #668: Kth Smallest Number in Multiplication Table
// class Solution {
// public int findKthNumber(int m, int n, int k) {
// int left = 1, right = m * n;
// while (left < right) {
// int mid = (left + right) >>> 1;
// int cnt = 0;
// for (int i = 1; i <= m; ++i) {
// cnt += Math.min(mid / i, n);
// }
// if (cnt >= k) {
// right = mid;
// } else {
// left = mid + 1;
// }
// }
// return left;
// }
// }
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
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.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.