Skip to content

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 the number 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 the number of numbers <= target.
    for (int i = 1; i <= m; ++i)
      count += Math.min(target / i, n);
    return count;
  }
}