class Solution {
public int findKthNumber(int m, int n, int k) {
int low = 1 , high = m * n + 1;
while (low < high) {
int mid = low + (high  low) / 2;
int c = count(mid, m, n);
if (c >= k) high = mid;
else low = mid + 1;
}
return high;
}
private int count(int v, int m, int n) {
int count = 0;
for (int i = 1; i <= m; i++) {
int temp = Math.min(v / i , n);
count += temp;
}
return count;
}
}
Java solution, binary search


@shawngao said in Java solution, binary search:
int temp = Math.min(v / i , n);
What is the meaning of this line? Count columns in each row? Why is it v / i?

@xuanyue_vol It counts all values smaller or equal than v in each column I guess. Using min is to avoid the count is larger than row number. It's a nice solution.


I am just wondering why this is not right? someone help me?
class Solution { public int findKthNumber(int m, int n, int k) { int low = 1; int high = m*n; while(low<high){ int mid = (low+high)>>>1; int cnt = count(m,n,mid); if(cnt == k){ return mid; } if(cnt<k){ low = mid+1; }else{ high = mid; } } return low; } public int count(int m,int n,int target){ int cnt = 0; for(int i = 1;i<=m;i++){ int temp = Math.min(target/i,n); cnt+=temp; } return cnt; } }

@tiandiao123 "mid" is not guaranteed to be an element in the m * n multiplication table... so when you have count == k, you could not just simply return number "mid". But I wonder why this method will guarantee that the answer is from the table.

@jun1013 @tiandiao123 The reason why when (count == k) we cannot return mid directly is that there might be multiple number mid assigned the cnt equals k. but only the smallest one is the right answer.
for example when m = 3, n = 2, k = 5:
1, 2, 3
2, 4, 6When mid = 5, k = cnt;
When mid = 4, k = cnt;
However, 5 is not in the multiplication table (5 % 2 != 0). Yet 4 is the right one


@jun1013 I don't think so. "mid" is guaranteed to be an element in the mn multiplication table. Because you can assume that when lo < k, it will not be the right answer, so lo = mid, but when the "ifelse" find the hi == k, it also means lo < k,so which element make this condition right? only when we have found the element hi (the right element) that made the counter increase, if mid is not in the mn multiplication table, the counter will not increase.
this is my code:
public int findKthNumber(int m, int n, int k) { int low = 0, high = 1000000000; while(high  low > 1){ int h = high+low>>1; int num = 0; for(int i = 1;i <= m;i++){ num += Math.min(h/i, n); } if(num < k){ low = h; }else{ high = h; } } return high; }

@xuanyue_vol
The count function is to find how many numbers in the table are less than or equal to value v. Since it is a multiplication table, and each number in the table is r*c, we can find the amount of numbers row by row (or column by column).For the first row, r=1, the maximum possible c is v/1=v, or n. Because c starts from 1, we can only have at most Math.min(v/1,n) values, which are less than or equal to v.
For the second row, r=2, the maximum c is v/2, or n. Similarly, we can only have at most Math.min(v/2,n) values.
For the ith row, r=i, the maximum c is v/i, or n.This is a really brilliant idea.

C++ version
class Solution { public: int findKthNumber(int m, int n, int k) { int left = 1, right = m*n+1; while (left < right) { int mid = left + (rightleft)/2; int cnt = count(m, n, mid); if (cnt >= k) right = mid; else left = mid + 1; } return right; } int count(int m, int n, int val) { int res = 0; int bound = min(m, val); // little optimization for (int i = 1; i <= bound; ++i) { res += min(n, val/i); } return res; } };

@DemonSong The reason I know why "mid" is not always from the multiplication table is that I tried to write down how this binary search work on paper. Say when you have a 4 by 6 table, the first "mid" you would have is obtained by "mid = 1 + (4 * 6 + 1  1) / 2" (as low = 1, high = m * n + 1 as defined in shawngao's method), then mid = 13 which is certainly not from the table. So there it is, but for the reason why this solution will always return a number that is from the table is that eventually you will hit something like count >= high, then high move to mid, that is some number from the table. I'd say this solution is very smart.



@victorzhang21503 You are right, the smallest number is the answer. But I'm confused how to guarantee the smallest number is in the table? I can see it from examples, but only a proof can convince me :)