LeetCode: Kth Smallest Number in Multiplication Table

Posted on June 18, 2019July 26, 2020 by braindenny

Kth Smallest Number in Multiplication Table

Similar Problems:

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:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/kth-smallest-number-in-multiplication-table
// Basic Ideas: dynamic programming
//
//  Given a number, how to check how many 
//     elements in matrix which are no bigger than the number
//
//  From left-bottom point, move up indicates decrease, move right indicates increase
//
//  From pos to value: (i, j) -> (i+1)*(j+1)
//
//  Monotonic function:
//   the bigger the value is, the more numbers which can be no bigger than it.
//
//  Notice: how we can be sure that we will hit the result?
//
// Complexity: Time O(m*log(m*n)), Sapce O(1)
func enoughNumbers(m int, n int, k int, target int) bool {
        count := 0
        i, j := m-1, 0
        for i>=0 && j<n {
                v := (i+1)*(j+1)
                if v <= target {
                        count += i+1
                        j++
                } else {
                        i--
                }
        }

        fmt.Println(k, target, count)
        return count >= k
}

func findKthNumber(m int, n int, k int) int {
        left, right := 1, m*n
        for left<right {
                mid := (right-left)/2+left
                // F, F, F, T, T, T, T
                if ! enoughNumbers(m, n, k, mid) {
                        // right half
                        left = mid+1
                } else {
                        right = mid
                }
        }
        return left
}

Post Views: 0