668. Kth Smallest Number in Multiplication Table

Problem

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 1:

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).

Example 2:

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).

Note:

1. The m and n will be in the range [1, 30000].
2. The k will be in the range [1, m * n]

Problem Summary

Almost everyone has used a multiplication table. But can you quickly find the k-th smallest number in a multiplication table? Given a multiplication table with height m and width n, and a positive integer k, you need to return the k-th smallest number in the table.

Note:

• m and n are in the range [1, 30000].
• k is in the range [1, m * n].

Solution Ideas

• Given 3 numbers, m, n, and k. m and n represent the rows and columns of the multiplication table respectively. The task is to find the k-th smallest number in this multiplication table.
• This problem is a variant of Problem 378. Use binary search to search for the k-th smallest number in the interval [1,m*n]. For each binary search step, count the number of values ≤ mid. Since we are counting in a matrix formed by multiplying two numbers, once the multiplier is known, the multiplicand is also known, so counting only requires one loop. The overall code is exactly the same as Problem 378; only the counting part is different. You can compare it with Problem 378 and practice them together.

Code

package leetcode

import "math"

func findKthNumber(m int, n int, k int) int {
	low, high := 1, m*n
	for low < high {
		mid := low + (high-low)>>1
		if counterKthNum(m, n, mid) >= k {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

func counterKthNum(m, n, mid int) int {
	count := 0
	for i := 1; i <= m; i++ {
		count += int(math.Min(math.Floor(float64(mid)/float64(i)), float64(n)))
	}
	return count
}