Leetcode Problem 668. Kth Smallest Number in Multiplication Table

668. Kth Smallest Number in Multiplication Table

Leetcode Solutions

Binary Search Approach

  1. Initialize lo to 1 and hi to m * n as the range of possible values for the kth smallest number.
  2. While lo is less than hi: a. Calculate mid as the average of lo and hi. b. Define enough(x) to count the number of values less than or equal to mid in the table. c. For each row i from 1 to m, add min(mid // i, n) to the count. d. If the count is at least k, set hi to mid. e. Otherwise, set lo to mid + 1.
  3. Return hi as the kth smallest number.
UML Thumbnail

Brute Force Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...