# 668. Kth Smallest Number in Multiplication Table

• Time: $O(m\log mn)$
• Space: $O(1)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: int findKthNumber(int m, int n, int k) { int l = 1; int r = m * n; auto numsNoGreaterThan = [&](int target) { int count = 0; // For each row i, count # of numbers <= target for (int i = 1; i <= m; ++i) count += min(target / i, n); return count; }; while (l < r) { const int mid = (l + r) / 2; if (numsNoGreaterThan(mid) >= k) r = mid; else l = mid + 1; } return l; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int findKthNumber(int m, int n, int k) { int l = 1; int r = m * n; while (l < r) { final int mid = (l + r) / 2; if (numsNoGreaterThan(m, n, mid) >= k) r = mid; else l = mid + 1; } return l; } private int numsNoGreaterThan(int m, int n, int target) { int count = 0; // For each row i, count # of numbers <= target for (int i = 1; i <= m; ++i) count += Math.min(target / i, n); return count; } }