# 668. Kth Smallest Number in Multiplication Table

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?
Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example:

Input: m = 3, n = 3, k = 5
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).
Input: m = 2, n = 3, k = 6
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

# Solution

Approach 1: brute force. Calculate all multiplication results, sort them, and pick out the kth. Time: O(mn*log(mn)).

Approach 2: heap. Observation: for each row, value[i+1] = value[i] + value[0]. So in a heap we store (value, row_number), and 'explore' a node by adding it's next smallest: (value + row_number, row_number). Time: O(m<heapify> + k*logm) -- good for small ks.

Approach 3: binary search. Observation: for each row, value[i] = (i+1) * value[0]. We can calculate total_nums<=x by adding up nums<=x for each row, then binary search for the first number that has at least k numbers less or equal to it. Time: O(log(mn) * m) -- the time doesn't have to do with k!

# Code (Python)

Approach 2:

import heapq
class Solution:
    def findKthNumber(self, m, n, k):
        """
        :type m: int
        :type n: int
        :type k: int
        :rtype: int
        """
        heap = [(row_num, row_num) for row_num in range(1, m+1)]
        heapq.heapify(heap)
        for i in range(k):
            value, row_num = heapq.heappop(heap)
            if i == k - 1:
                return value
            if value + row_num <= row_num * n:
                heapq.heappush(heap, (value + row_num, row_num))

Approach 3:

    def findKthNumber(self, m, n, k):
        left, right = 1, m * n
        while left < right:
            mid = (left + right) // 2
            nums_less_or_equal = self._nums_less_or_equal_to(mid, m, n)
            if nums_less_or_equal >= k:
                right = mid # if nums_less_or_equal == k, we can return mid immediately
            else:
                left = mid + 1
        return left
    
    # need to count in the nums equal to the target too, otherwise we get the (k+1)th smallest
    def _nums_less_or_equal_to(self, target, m, n):
        total = 0
        for row_num in range(1, m + 1):
            total += min(n, target // row_num)
        return total

# Code (C++)

Approach 1:

Approach 2:

Approach 3: