C++ fast and short O(mlog(m*n)) solution, beats 100%


  • 0
    M
        int findKthNumber(int m, int n, int k) {
            int l=1, h=m*n, mid=l+(h-l)/2;
            while(l<h) {
                int p=0, p0=0;
                for(int j=0;j<m;j++) {
                    p+=min(mid/(j+1), n);
                    p0+=min((mid-1)/(j+1), n);
                }
                if(k>p0&&k<=p) return mid;
                else if(p0>=k) h=mid;
                else if(p<k) l=mid+1;
                mid=l+(h-l)/2;
            }
            return mid;
        }

Log in to reply
 

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