Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

668. Kth Smallest Number in Multiplication Table

Time: $O(m\log mn)$

Space: $O(1)$

			


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;
  }
};




			


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;
  }
}