We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Kth Smallest Number in Multiplication Table

Difficulty: Hard

Problem Description

Given three integers m, n, and k, return the k-th smallest element in the m x n multiplication table, where mat[i][j] == i * j (1-indexed).

Key Insights

  • The multiplication table is sorted in a specific manner where each row is sorted, and each column is also sorted.
  • The k-th smallest number can be efficiently found using binary search.
  • The count of numbers less than or equal to a certain value can be calculated without explicitly constructing the entire multiplication table.

Space and Time Complexity

Time Complexity: O(m log(n * m))
Space Complexity: O(1)

Solution

To solve the problem, we will use a binary search approach. The idea is to search for the k-th smallest number in the range from 1 to m * n. For a mid value in this range, we will count how many numbers in the multiplication table are less than or equal to mid. If this count is greater than or equal to k, then we know the k-th smallest number must be less than or equal to mid. If the count is less than k, then we need to look for larger numbers.

The algorithm employs:

  • A binary search to narrow down the possible values of the k-th smallest number.
  • A counting mechanism to determine how many values are less than or equal to the current mid value.

Code Solutions

def findKthNumber(m: int, n: int, k: int) -> int:
    def count_less_equal(x):
        count = 0
        for i in range(1, m + 1):
            count += min(x // i, n)  # count how many numbers are <= x
        return count

    left, right = 1, m * n
    while left < right:
        mid = (left + right) // 2
        if count_less_equal(mid) < k:
            left = mid + 1
        else:
            right = mid
    return left
← Back to All Questions