# Kth Smallest Number in Multiplication Table

This page explains Java solution to problem `Kth Smallest Number in Multiplication Table` using `Binary Search` algorithm.

## Problem Statement

Nearly every one have used the Multiplication Table. But could you find out the `k-th` smallest number quickly from the multiplication table?

Given the height m and the length `n` of a `m * n` Multiplication Table, and a positive integer `k`, you need to return the `k-th` smallest number in this table.

Example 1:

Input: m = 3, n = 10, k = 5
Output: 3
Explanation: The Multiplication Table:
1 2 3
2 4 6
3 6 9
The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

Input: m = 2, n = 3, k = 6
Output: 6
Explanation: The Multiplication Table:
1 2 3
2 4 6
The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

class KthSmallestNumberInMultiplicationTable {
public int findKthNumber(int m, int n, int k) {
int lo = 0;
int hi = m * n;
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
int index = getIndex(m, n, mid);
if(index < k) lo = mid + 1;
else hi = mid - 1;
}
return lo;
}

private int getIndex(int m, int n, int number) {
int row = 1;
int col = n;
int numberIndex = 0;
while(row <= m && col > 0) {
if(row * col <= number) {
numberIndex += col;
row++;
}
else col--;
}
return numberIndex;
}
}

``````

O(MN log MN)

O(1)