Given three integers M, N and K. Consider a grid of M * N, where mat[i][j] = i * j (1 based index). The task is to return the K^{th} smallest element in the M * N multiplication table.
 
Example 1:
Input:
M = 3, N = 3
K = 5
Output: 3
Explanation: 
The 5^{th} smallest element is 3. 
Example 2:
Input:
M = 2, N = 3
K = 6
Output: 6 
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function KthSmallest() which takes three integers as input and returns an integer as output.
Expected Time Complexity: O(M * log(M * N))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= M, N <= 3 * 10^{4}
1 <= K <= M * N

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Sorting

Starter code: class Solution(object):

    def findKthNumber(self, m, n, k):

        #Write your code here

Solutions:
class Solution(object):

	def findKthNumber(self, m, n, k):
		(lo, hi) = (0, m * n + 1)
		while lo < hi:
			mid = (lo + hi) // 2
			val = 0
			for i in range(m):
				val += min(n, mid // (i + 1))
			if val >= k:
				hi = mid
			else:
				lo = mid + 1
		return hi


class Solution(object):

	def findKthNumber(self, m, n, k):
		(low, high) = (1, m * n)
		kth_guess = 0
		while low <= high:
			guess = low + (high - low) // 2
			(i, j) = (m, 1)
			count = 0
			while i > 0 and j <= n:
				if i * j <= guess:
					count += i
					j += 1
				else:
					i -= 1
			if count >= k:
				kth_guess = guess
				high = guess - 1
			else:
				low = guess + 1
		return kth_guess


class Solution(object):

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


class Solution(object):

	def findKthNumber(self, m, n, k):
		s = 1
		e = m * n
		while s <= e:
			mid = (s + e) // 2
			c = 0
			for i in range(1, m + 1):
				c += min(n, mid // i)
			if c >= k:
				ans = mid
				e = mid - 1
			else:
				s = mid + 1
		return ans


class Solution(object):

	def findKthNumber(self, m, n, k):

		def check(e):
			q = 0
			for l in range(1, m + 1):
				q += min(e // l, n)
			return q
		i = 1
		j = m * n
		while i <= j:
			mid = (i + j) // 2
			z = check(mid)
			if z >= k:
				j = mid - 1
			else:
				i = mid + 1
		return i


class Solution(object):

	def findKthNumber(self, m, n, k):

		def count(x):
			count = 0
			for i in range(1, m + 1):
				count += min(x // i, n)
			return count
		(l, r) = (1, m * n)
		while l < r:
			mid = (l + r) // 2
			if count(mid) < k:
				l = mid + 1
			else:
				r = mid
		return l


class Solution(object):

	def position(self, m, n, k):
		r = m - 1
		c = 0
		res = 0
		while r >= 0 and c < n:
			if (r + 1) * (c + 1) > k:
				r -= 1
			else:
				res += r + 1
				c += 1
		return res

	def binarysearch(self, l, r, m, n, k):
		if l <= r:
			mid = (l + r) // 2
			cou = self.position(m, n, mid)
			if cou >= k:
				return self.binarysearch(l, mid - 1, m, n, k)
			else:
				return self.binarysearch(mid + 1, r, m, n, k)
		return l

	def findKthNumber(self, m, n, k):
		return self.binarysearch(1, m * n, m, n, k)


class Solution(object):

	def findKthNumber(self, m, n, k):
		low = 1
		high = m * n
		while low <= high:
			mid = (low + high) // 2
			if self.Count(mid, m, n) < k:
				low = mid + 1
			elif self.Count(mid - 1, m, n) < k:
				return mid
			else:
				high = mid - 1

	def Count(self, mid, m, n):
		cnt = 0
		for i in range(1, m + 1):
			temp = mid // i
			if temp > n:
				cnt += n
			else:
				cnt += temp
		return cnt


import heapq as heap

class Solution(object):

	def findKthNumber(self, m, n, k):
		(lo, hi) = (1, m * n)
		while lo < hi:
			mid = (lo + hi) // 2
			val = 0
			for i in range(1, m + 1):
				val += min(n, mid // i)
			if val >= k:
				hi = mid
			else:
				lo = mid + 1
		return hi
t = int(input())
for _ in range(0, t):
	arr = list(map(int, input().split()))
	ob = Solution()
	print(ob.findKthNumber(arr[0], arr[1], arr[2]))


class Solution(object):

	def findKthNumber(self, m, n, k):
		(a, b) = (0, m * n + 1)
		while a < b:
			mid = (a + b) // 2
			val = 0
			for i in range(m):
				val += min(n, mid // (i + 1))
			if val >= k:
				b = mid
			else:
				a = mid + 1
		return b
t = int(input())
for _ in range(0, t):
	arr = list(map(int, input().split()))
	ob = Solution()
	print(ob.findKthNumber(arr[0], arr[1], arr[2]))


class Solution(object):

	def findKthNumber(self, m, n, k):
		low = 1
		high = m * n
		while low <= high:
			mid = (low + high) // 2
			count = 0
			for i in range(1, m + 1):
				count = count + min(n, mid // i)
			if count >= k:
				high = mid - 1
			else:
				low = mid + 1
		return low
t = int(input())
for _ in range(0, t):
	arr = list(map(int, input().split()))
	ob = Solution()
	print(ob.findKthNumber(arr[0], arr[1], arr[2]))


class Solution(object):

	def findKthNumber(self, m, n, k):

		def helper(target):
			return sum((min(target // i, n) for i in range(1, m + 1)))
		start = 0
		end = (m + 1) * (n + 1)
		while start <= end:
			mid = start + (end - start) // 2
			if helper(mid) < k:
				start = mid + 1
			else:
				end = mid - 1
		return start


class Solution(object):

	def findKthNumber(self, x, y, k):
		if k > x * y:
			return x * y
		return self.bns(x, y, k)

	def bns(self, x, y, k):
		hi = x * y
		lo = 1
		res = 0
		while hi > lo:
			mid = hi + lo >> 1
			tot = self.cal(x, y, mid)
			if tot >= k:
				hi = mid
			else:
				res = mid
				lo = mid + 1
		return hi

	def cal(self, x, y, mid):
		res = 0
		for n in range(1, y + 1):
			res += min(x, mid // n)
		return res


class Solution(object):

	def findKthNumber(self, m, n, k):

		def valid(mid):
			count = 0
			for i in range(1, m + 1):
				count += min(mid // i, n)
				if count >= k:
					return True
			return False
		l = 1
		r = m * n
		ans = None
		while l <= r:
			mid = l + (r - l) // 2
			if valid(mid):
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution(object):

	def is_valid(self, num, m, n, k):
		min_values = 0
		for i in range(1, m + 1):
			tmp = min(num // i, n)
			min_values += tmp
			if min_values >= k:
				return True
			if tmp == 0:
				break
		return False

	def findKthNumber(self, m, n, k):
		left = 1
		right = m * n
		while left < right:
			mid = left + (right - left) // 2
			if self.is_valid(mid, m, n, k):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def findKthNumber(self, m: int, n: int, k: int) -> int:

		def f(target):
			return sum((min(target // i, n) for i in range(1, m + 1)))
		(lo, hi) = (0, (m + 1) * (n + 1))
		while lo < hi:
			mid = (lo + hi) // 2
			if f(mid) >= k:
				hi = mid
			else:
				lo = mid + 1
		return lo


class Solution(object):

	def findKthNumber(self, m, n, k):
		l = 1
		h = m * n
		while l <= h:
			mid = l + (h - l) // 2
			cnt = 0
			for i in range(1, m + 1):
				cnt += min(n, mid // i)
			if cnt >= k:
				h = mid - 1
			else:
				l = mid + 1
		return l


class Solution(object):

	def findKthNumber(self, m, n, k):

		def getSum(mid):
			return sum([min(mid // i, n) for i in range(1, m + 1)]) >= k
		lo = 1
		hi = m * n
		while lo < hi:
			mid = lo + (hi - lo) // 2
			if not getSum(mid):
				lo = mid + 1
			else:
				hi = mid
		return lo


class SolutionNaive:

	def findKthNumber(self, m: int, n: int, k: int) -> int:
		firstrow = range(1, n + 1)
		firstcol = range(1, m + 1)
		table = [i * j for (i, j) in product(firstrow, firstcol)]
		table.sort()
		return table[k - 1]

class Solution:

	def findKthNumber(self, m: int, n: int, k: int) -> int:
		if m > n:
			(m, n) = (n, m)

		def check(index):
			count = 0
			for row in range(1, m + 1):
				count += min(index // row, n)
			return count < k
		l = 1
		r = n * m
		while l < r:
			mid = (l + r) // 2
			if check(mid):
				l = mid + 1
			else:
				r = mid
		return l


class Solution(object):

	def findKthNumber(self, m, n, k):

		def count(target, m, n):
			return sum((min(target // i, n) for i in range(1, m + 1)))
		(left, right) = (1, m * n)
		while left <= right:
			mid = left + (right - left) // 2
			if count(mid, m, n) >= k:
				right = mid - 1
			else:
				left = mid + 1
		return left


class Solution(object):

	def findKthNumber(self, m, n, k):
		low = 1
		high = m * n
		while low <= high:
			mid = low + (high - low) // 2
			count = self.getSmallerNum(m, n, mid)
			if count < k:
				low = mid + 1
			else:
				high = mid - 1
		return low

	def getSmallerNum(self, m, n, k):
		row = m - 1
		col = 0
		res = 0
		while row >= 0 and col < n:
			if (row + 1) * (col + 1) > k:
				row -= 1
			else:
				res += row + 1
				col += 1
		return res


class Solution(object):

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


class Solution(object):

	def findKthNumber(self, m, n, k):

		def count(x):
			return sum((min(x // i, n) for i in range(1, m + 1)))
		(L, R, mid, ans) = (0, m * n, 0, 0)
		while L <= R:
			mid = L + R >> 1
			if count(mid) < k:
				L = mid + 1
			else:
				(R, ans) = (mid - 1, mid)
		return ans


from heapq import *

class Solution(object):

	def findKthNumber(self, M, N, k):

		def lessOrEqualToMid(mid):
			count2 = 0
			for i in range(1, min(N + 1, mid + 1)):
				count2 += min(M, mid // i)
			return count2
		(lo, hi) = (1, M * N + 1)
		while lo < hi:
			mid = lo + hi >> 1
			count2 = lessOrEqualToMid(mid)
			if count2 < k:
				lo = mid + 1
			else:
				hi = mid
		return lo


import heapq

class Solution(object):

	def findKthNumber1(self, m, n, k):
		heap = []
		for i in range(1, m + 1):
			for j in range(1, n + 1):
				prod = i * j
				heapq.heappush(heap, prod)
		for _ in range(k - 1):
			tmp = heapq.heappop(heap)
		return heapq.heappop(heap)

	def counter(self, m, n, mid):
		count = 0
		for i in range(1, m + 1):
			count += min(n, mid // i)
		return count

	def findKthNumber(self, m, n, k):
		(l, r) = (0, m * n)
		while l <= r:
			mid = (l + r) // 2
			count = self.counter(m, n, mid)
			if count < k:
				l = mid + 1
			else:
				r = mid - 1
		return l


class Solution(object):

	def findKthNumber(self, m, n, k):

		def isless(x):
			return sum([min(x // i, n) for i in range(1, m + 1)]) >= k
		beg = 1
		end = m * n
		while beg < end:
			mid = (beg + end) // 2
			if not isless(mid):
				beg = mid + 1
			else:
				end = mid
		return beg


def calc(x, k, n, m):
	ans = 0
	for i in range(1, m + 1):
		ans += min(x // i, n)
	return ans >= k

def optimal(m, n, k):
	st = 1
	en = m * n
	while st < en:
		mid = (st + en) // 2
		if calc(mid, k, n, m):
			en = mid
		else:
			st = mid + 1
	return st

class Solution(object):

	def findKthNumber(self, m, n, k):
		return optimal(m, n, k)


class Solution(object):

	def findKthNumber(self, m, n, k):

		def enough(x):
			count = 0
			for i in range(1, m + 1):
				count += min(x // i, n)
			return count >= k
		(lo, hi) = (1, m * n)
		while lo < hi:
			mi = (lo + hi) // 2
			if not enough(mi):
				lo = mi + 1
			else:
				hi = mi
		return lo


class Solution(object):

	def findKthNumber(self, r, c, x):

		def count(x):
			res = 0
			for i in range(1, r + 1):
				res += min(x // i, c)
			return res
		(left, right) = (1, r * c)
		ans = right
		while left <= right:
			m = (right + left) // 2
			if count(m) < x:
				left = m + 1
			else:
				ans = min(ans, m)
				right = m - 1
		return ans