Problem 374131 · hard · Level 03 Linear Management & Searching

The k-th Cell of a Signed Times Table

binary search on the answer · sorting · counting · integer division

A teacher writes a times table whose row labels are rows and whose column labels are cols. Both lists are sorted ascending and may contain negatives, zeros and repeats. The cell for row i and column j holds rows[i] * cols[j], so the table has len(rows) * len(cols) cells.

Sort all cell values ascending (repeats kept) and return the k-th one, 1-based.

Examples

Input:  rows = [-2, 0, 3], cols = [-1, 4], k = 2
Output: -3
Explanation: the cells are 2, -8, 0, 0, -3, 12; sorted: -8, -3, 0, 0, 2, 12.

Input:  rows = [-3, -1], cols = [-5, 2, 2], k = 5
Output: 5
Explanation: sorted cells: -6, -6, -2, -2, 5, 15.

Constraints

  • 1 <= len(rows), len(cols) <= 10**4
  • -10**5 <= rows[i], cols[j] <= 10**5, both lists sorted ascending
  • 1 <= k <= len(rows) * len(cols)
  • The table can have 10**8 cells, so it cannot be built.

Goals

  • Count products at most x when the factors can be negative, zero or positive
  • Use floor and ceiling division correctly with negative numbers
Starting Python…