Java solution, binary search


  • 33
    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;
        }
    }
    

  • 0
    X

    @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?


  • 3
    J

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


  • 1

    Python version:

    def findKthNumber(self, m, n, k):
            low, high = 1, m * n + 1
        	while low < high:
        	    mid = (high + low) / 2
        	    c = sum(min(mid / i , n) for i in range(1, m + 1))
        	    if c >= k: high = mid
                else: low = mid + 1
        	return high

  • 0
    A

    @jiayi.zhang1993
    Each row instead, I guess you have other way of visualization.


  • 0
    Z

    Great answer!


  • 1
    T

    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;
        }
    }
    
    

  • 0

    Nice solution!


  • 3
    J

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


  • 4

    @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, 6

    When 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


  • 1
    T

    @victorzhang21503 Oh,I see! Thank you for your explanation!


  • 1
    M

    Thanks for sharing. The count() function is smart.
    But, it seems that "high = m * n" is also OK, it's not necessary to plus 1.


  • 0
    D

    @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 "if-else" 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;
     }
    

  • 3
    L

    @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 i-th row, r=i, the maximum c is v/i, or n.

    This is a really brilliant idea.


  • 0

    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 + (right-left)/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;
        }
    };
    

  • 1
    J

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


  • 1
    T

    hi, I was wondering how did you come up with the idea of binary search?
    hope to get some insight, thx in advance


  • 0
    A

    @shawngao The way you have leveraged Binary Search is brilliant!


  • 0
    A

    @Longji Exactly, this is what I was unable to grap!


  • 0
    T

    @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 :)


Log in to reply
 

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