668. Kth Smallest Number in Multiplication Table

📋 Đề Bài

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 k^th smallest element in the m x n multiplication table.

Example 1:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5^th smallest number is 3.

Example 2:

Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The 6^th smallest number is 6.

Constraints:

1 <= m, n <= 3 * 10⁴
1 <= k <= m * n

🧠 Thuật Toán & Kỹ Thuật

Binary Search (Tìm kiếm nhị phân)

⏱️ Thời gian O(log n)

💾 Không gian O(1)

💻 Lời Giải

C++ 0668-kth-smallest-number-in-multiplication-table.cpp

class Solution {
public:
    int findKthNumber(int m, int n, int k) {
        long long left = 1;
        long long right = m*n;
        long long ans = 0;
        
        while (left <= right) {
            long long mid = (left + right) / 2;
            long long cnt = 0;
            
            for (int i = 1; i <= m; ++i) {
                cnt += min(mid / i, n*1LL);
            }
            
            if (cnt >= k) {
                ans = mid;
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        
        return ans;
    }
};