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.

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

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

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

Time Complexity

O(MN log MN)

Space Complexity

O(1)