Solution by awice

• Approach #1: Brute Force [Memory Limit Exceeded]

Intuition and Algorithm

Create the multiplication table and sort it, then take the k-th element.

Python

``````class Solution(object):
def findKthNumber(self, m, n, k):
table = [i*j for i in range(1, m+1) for j in range(1, n+1)]
table.sort()
return table[k-1]
``````

Java

``````class Solution {
public int findKthNumber(int m, int n, int k) {
int[] table = new int[m*n];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
table[(i - 1) * n + j - 1] = i * j;
}
}
Arrays.sort(table);
return table[k-1];
}
}
``````

Complexity Analysis

• Time Complexity: \$\$O(mn)\$\$ to create the table, and \$\$O(mn\log(m*n))\$\$ to sort it.

• Space Complexity: \$\$O(m*n)\$\$ to store the table.

Approach #2: Next Heap [Time Limit Exceeded]

Intuition

Maintain a heap of the smallest unused element of each row. Then, finding the next element is a pop operation on the heap.

Algorithm

Our `heap` is going to consist of elements `(val, root)`, where `val` is the next unused value of that row, and `root` was the starting value of that row.

We will repeatedly find the next lowest element in the table. To do this, we pop from the heap. Then, if there's a next lowest element in that row, we'll put that element back on the heap.

Python

``````class Solution(object):
def findKthNumber(self, m, n, k):
heap = [(i, i) for i in range(1, m+1)]
heapq.heapify(heap)

for _ in xrange(k):
val, root = heapq.heappop(heap)
nxt = val + root
if nxt <= root * n:
heapq.heappush(heap, (nxt, root))

return val
``````

Java

``````class Solution {
public int findKthNumber(int m, int n, int k) {
PriorityQueue<Node> heap = new PriorityQueue<Node>(m,
Comparator.<Node> comparingInt(node -> node.val));

for (int i = 1; i <= m; i++) {
heap.offer(new Node(i, i));
}

Node node = null;
for (int i = 0; i < k; i++) {
node = heap.poll();
int nxt = node.val + node.root;
if (nxt <= node.root * n) {
heap.offer(new Node(nxt, node.root));
}
}
return node.val;
}
}

class Node {
int val;
int root;
public Node(int v, int r) {
val = v;
root = r;
}
}
``````

Complexity Analysis

• Time Complexity: \$\$O(k * m \log m) = O(m^2 n \log m)\$\$. Our initial heapify operation is \$O(m)\$. Afterwards, each pop and push is \$\$O(m \log m)\$\$, and our outer loop is \$\$O(k) = O(m*n)\$\$

• Space Complexity: \$\$O(m)\$\$. Our heap is implemented as an array with \$\$m\$\$ elements.

Approach #3: Binary Search [Accepted]

Intuition

As `k` and `m*n` are up to \$\$9 * 10^8\$\$, linear solutions will not work. This motivates solutions with `\log` complexity, such as binary search.

Algorithm

Let's binary search for the answer `A`.

Say `enough(x)` is true if and only if there are `k` or more values in the multiplication table that are less than or equal to `x`. Colloquially, `enough` describes whether `x` is large enough to be the `k-th` value in the multiplication table.

Then (for our answer `A`), whenever `x >= A`, `enough(x)` is `True`; and whenever `x < A`, `enough(x)` is `False`.

In our binary search, our loop invariant is that `enough(hi) = True`. At the beginning, `enough(m*n) = True`, and whenever `hi` is set, it is set to a value that is "enough" (`enough(mi) = True`). That means `hi` will be the lowest such value at the end of our binary search.

This leaves us with the task of counting how many values are less than or equal to `x`. For each of `m` rows, the `i`-th row looks like `[i, 2*i, 3*i, ..., n*i]`. The largest possible `k*i <= x` that could appear is `k = x // i`. However, if `x` is really big, then perhaps `k > n`, so in total there are `min(k, n) = min(x // i, n)` values in that row that are less than or equal to `x`.

After we have the count of how many values in the table are less than or equal to `x`, by the definition of `enough(x)`, we want to know if that count is greater than or equal to `k`.

Python

``````class Solution(object):
def findKthNumber(self, m, n, k):
def enough(x):
count = 0
for i in xrange(1, m+1):
count += min(x // i, n)
return count >= k

lo, hi = 1, m * n
while lo < hi:
mi = (lo + hi) / 2
if not enough(mi):
lo = mi + 1
else:
hi = mi
return lo
``````

Java

``````class Solution {
public boolean enough(int x, int m, int n, int k) {
int count = 0;
for (int i = 1; i <= m; i++) {
count += Math.min(x / i, n);
}
return count >= k;
}

public int findKthNumber(int m, int n, int k) {
int lo = 1, hi = m * n;
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (!enough(mi, m, n, k)) lo = mi + 1;
else hi = mi;
}
return lo;
}
}
``````

Complexity Analysis

• Time Complexity: \$\$O(m * \log (m*n))\$\$. Our binary search divides the interval `[lo, hi]` into half at each step. At each step, we call `enough` which does \$\$O(m)\$\$ work.

• Space Complexity: \$\$O(1)\$\$. We only keep integers in memory during our intermediate calculations.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.