LeetCode 668: Kth Smallest Number in Multiplication Table Solution

Master LeetCode problem 668 (Kth Smallest Number in Multiplication Table), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

668. Kth Smallest Number in Multiplication Table

Hard

Math Binary Search

Problem Explanation

Explanation:

To find the kth smallest number in the multiplication table, we can perform a binary search on the range of possible values. The key observation is that the numbers in the multiplication table are sorted row-wise and column-wise. We can use binary search to find the smallest number x such that there are exactly k numbers in the table that are less than or equal to x.

Initialize the range of possible values from 1 to m * n.
Perform a binary search on this range.
For each mid value, count the number of elements in the table that are less than or equal to mid by iterating through each row and finding the number of elements less than or equal to mid in that row.
Update the search range based on the count of elements less than or equal to mid.

Time Complexity: O(m * log(m*n)) Space Complexity: O(1)

Solution Code

class Solution {
    public int findKthNumber(int m, int n, int k) {
        int lo = 1, hi = m * n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            int count = 0;
            for (int i = 1; i <= m; i++) {
                count += Math.min(mid / i, n);
            }
            if (count < k) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 668 (Kth Smallest Number in Multiplication Table)?

This page provides optimized solutions for LeetCode problem 668 (Kth Smallest Number in Multiplication Table) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 668 (Kth Smallest Number in Multiplication Table)?

The time complexity for LeetCode 668 (Kth Smallest Number in Multiplication Table) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 668 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 668 in Java, C++, or Python.

Back to LeetCode Solutions