# clear java solution! fastest!

• Binary Search within a range [Accepted]

Intuition

1. `if (m > n)`, we can transpose the multiplication table, of which the result doesn't change. So we can always deal with a multiplication table with `n >= m`.

2. Consider a function `int countUnder(int m, int n, int target)`, which counts the number of numbers in a `m * n` multiplication table that is less than or equal to target.
Note:

• target can be any non-negative integer, which may not be in the multiplication table
• if target is a number in the multiplication table, then `countUnder(m, n, target) > countUnder(m, n, target - 1)`. But if target is not in the multiplication table, then `countUnder(m, n, target) = countUnder(m, n, target - 1)`.
1. Now we only need to find a number `kthNumber`, s.t. `countUnder(m, n, kthNumber) >= k > countUnder(m, n, kthNumber - 1)`, then `kthNumber` is the largest k-th number we want to find.

2. Actually, we can deduce the for analytical representation of the function `int countUnder(int m, int n, int target)` and then derive a range for `kthNumber`. The detailed process is in the attachment. [0_1504103360984_derivation.pdf](Uploading 100%)
After getting the range, we can use binary search to get the `kthNumber`.

algorithm

``````class Solution {
static int countUnder(int m, int n, int target) {
int l = target / n;
int result = l * n;
for(int i = l + 1; i <= m; i += 1) {
result += target / i;
}
return result;
}

public int findKthNumber(int m, int n, int k) {
// if m > n, we transpose the table, which doesn't change the result
// So we can assure that m <= n
if(m > n) {
int a = m;
m = n;
n = a;
}

// the kth largest number we want to find
int kthNumber = 0;
// find l, s.t. l < double(kthNumber) / n <= l + 1
// using binary search
int l = 0;
int start = 0;
int end = m - 1;
while(start < end) {
int middle = (start + end) / 2;
int nums = countUnder(m, n, (middle + 1) * n);
if(k <= nums)
end = middle;
else
start = middle + 1;
}
// now start == end
l = start;

// calculate the range that the k-th largest number can be in
double aux = 0.0;
for(int i = l + 1; i <= m; i += 1) {
aux += 1.0 / i;
}
int min = (int)Math.ceil((k - n * l) / aux);
// a trick, (int)Math.ceil(a - 1) = a - 1 if a = integer
//                                = (int) a, if a not integer
int max = (int)Math.ceil((k - n * l + m - l) / aux - 1);

// using binary search to find the k-th largest number
start = Math.max(min, n * l + 1);
end = Math.min(max, n * (l + 1));
while(start < end) {
int middle = (start + end) / 2;
if(k <= countUnder(m, n, middle))
end = middle;
else
start = middle + 1;
}
// now start == end
kthNumber = start;
return kthNumber
}

``````

Complexity Analysis

• Time Complexity: O(min(m, n) * log(min(m,n)))
• Space Complexity: O(1)

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