leetcode-go/hard/668.kth-smallest-number-in-multiplication-table.go

func findKthNumber(m int, n int, k int) int {
	beg, end := 1, m*n
	for beg <= end {
		mid := beg + (end-beg)/2
		if rank(m, n, mid) < k {
			beg = mid + 1
		} else {
			end = mid - 1
		}
	}
	return beg
}

func rank(m, n, x int) (cnt int) {
	// Find the rank row by row.
	// Assume that x is in the ith row:
	// 1*i 2*i 3*i ... n*i, then
	// x/i is in row 1 2 3 ... n,
	// so x is the (x/i)th num.
	for i := 1; i <= m; i++ {
		cnt += minInt(n, x/i)
	}
	return cnt
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}