Kth Smallest Number in Multiplication Table LeetCode solution in C++

1
class Solution {
2
 public:
3
  int findKthNumber(int m, int n, int k) {
4
    int high = m * n, low = 1;
5

6
    int mid = 0, ans = 1e9;
7
    while (low <= high) {
8
      mid = low + (high - low) / 2;
9
      int temp = 0;
10

11
      // for each i find the max value ,less than or equal to n , such that
12
      // i*j<=mid
13
      // add j to answer
14
      for (int i = 1; i <= m; i++) temp += min(mid / i, n);
15

16
      if (temp >= k) {
17
        ans = min(ans, mid);
18
        high = mid - 1;
19
      } else
20
        low = mid + 1;
21
    }
22
    return ans;
23
  }
24
};