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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Kth Smallest Number in Multiplication Table

Number: 668

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given a multiplication table of size m x n where mat[i][j] = i * j (1-indexed), find the kth smallest number in the table.

Key Insights

  • The table elements are not fully sorted row-wise or column-wise globally, but there is a pattern that can be exploited.
  • For any candidate number x, we can count how many numbers in the table are less than or equal to x by summing over rows: for row i, there are min(x // i, n) numbers.
  • Binary search can be used over the range [1, m*n] to find the smallest x such that the count is at least k.
  • The counting function is the key to connecting the candidate value with the order statistic.

Space and Time Complexity

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

Solution

We use binary search over the possible values in the multiplication table, which range from 1 to m*n. For each midpoint x in the binary search, we compute the number of elements in the table that are less than or equal to x by iterating over each row and summing up min(x // i, n). This count tells us whether the kth smallest element is to the left or right of x. We then adjust the binary search boundaries accordingly. The approach leverages the multiplicative structure of the table and the monotonicity of the counting function.

Code Solutions

# Python solution using binary search

class Solution:
    def findKthNumber(self, m: int, n: int, k: int) -> int:
        def count_less_equal(x: int) -> int:
            # Count numbers in the m x n multiplication table <= x
            count = 0
            for i in range(1, m + 1):
                # For each row, count of numbers <= x is minimum of n or x // i
                count += min(x // i, n)
            return count

        # Binary search range from 1 to m*n
        low, high = 1, m * n
        while low < high:
            mid = (low + high) // 2
            if count_less_equal(mid) >= k:
                high = mid  # mid might be the answer
            else:
                low = mid + 1  # answer must be greater than mid
        return low
← Back to All Questions