DeepSeek LeetCode 668. Kth Smallest Number in Multiplication Table Java Implement

Here is the Java implementation for LeetCode 668. Kth Smallest Number in Multiplication Table, using the standard Binary Search on Value approach.

1. Core Idea

The multiplication table is far too large to materialize (up to 9 \times 10^8 cells). Instead of finding the k-th number directly, we solve a reverse problem:

Given a value x, how many entries in the table are less than or equal to x?

This count is easy to compute:

· In the i-th row, the entries are i1, i2, …, i*n. The number of entries ≤ x is simply min(x / i, n).
· Summing this over all rows gives count(x).

The function count(x) is monotonically non-decreasing as x increases. Therefore, we can binary search for the smallest x such that count(x) >= k. This x is guaranteed to be the k-th smallest number in the table.

2. Java Implementation (Standard Binary Search)

classSolution{publicintfindKthNumber(intm,intn,intk){intlo=1;inthi=m*n;while(lo<hi){intmid=lo+(hi-lo)/2;intcount=0;// Count how many entries are <= midfor(inti=1;i<=m;i++){count+=Math.min(mid/i,n);// Early exit if we already have enoughif(count>=k)break;}if(count>=k){hi=mid;// mid could be the answer; search left}else{lo=mid+1;// mid is too small; search right}}returnlo;}}

This code is adapted from the standard solution provided in the LeetCode community.

3. Complexity Analysis

Metric Complexity Explanation
Time O(m \log(m \cdot n)) Binary search takes O(\log(m \cdot n)) iterations, and each iteration scans up to m rows.
Space O(1) Only a few integer variables are used.

4. Possible Optimization (Optional)

The standard loop iterates over all m rows. However, for rows where i \le \lfloor mid / n \rfloor, every entry in that row is \le mid. This creates a “saturated block” of rows where count is simply n per row.

We can sum these rows in O(1) using multiplication, and only loop over the remaining rows. This reduces the inner loop from O(m) to O(\sqrt{mid}), bringing the total time down to O(\sqrt{m \cdot n} \log(m \cdot n)). For the given constraints, the standard version is already sufficient.

Key Note: Use long for the count variable if you are concerned about integer overflow, although for m, n ≤ 30,000, the maximum total count (9 × 10^8) still fits within a 32-bit signed integer. The mid variable also fits in int.