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.
classSolution { public: intfindKthNumber(int m, int n, int k){ int lo = 0, hi = m * n + 1; int res = INT_MAX; while(lo <= hi) { int mi = lo + (hi - lo) / 2; int count = getCount(mi, m, n); if(count >= k) res = min(res,mi); if(count < k) lo = mi + 1; else hi = mi - 1; } return res; } intgetCount(int value, int m, int n){ int res = 0; for(int i = 1; i <= m; i++) { res += min(value / i, n); } return res; } };