Show problems as
Classic problem #2300MediumArrayTwo PointersBinary SearchSorting

Successful Pairs of Spells and Potions

Real-world version: Dies That Hold Against Each Press
Tracked in this browser only
Read Successful Pairs of Spells and Potions on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A workshop has presses with forces presses and dies with ratings dies. Pairing a press with a die makes a stamp whose strength is the two numbers multiplied, and the pairing holds when that strength is at least target.

Return a list whose entry i says how many of the dies hold when paired with press i.

Examples

Example 1

Input
presses = [2, 4, 6], dies = [5, 3, 1], target = 10
Output
[1, 2, 2]

The weakest press reaches the target only with the highest-rated die. Each of the other two presses manages it with two dies.

Example 2

Input
presses = [3], dies = [3], target = 9
Output
[1]

Three times three lands exactly on the target, and a pairing holds when it reaches the target rather than having to pass it.

Example 3

Input
presses = [1, 2, 3, 4, 5], dies = [1], target = 5
Output
[0, 0, 0, 0, 1]

The single die is rated 1, so a press holds only when its own force reaches the target.

Constraints

  • 1 <= presses.length <= 10^5
  • 1 <= dies.length <= 10^5
  • 1 <= presses[i] <= 10^5
  • 1 <= dies[i] <= 10^5
  • 1 <= target <= 10^10

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def successful_pairs(presses: list[int], dies: list[int], target: int) -> list[int]:
Java
public int[] successfulPairs(int[] presses, int[] dies, long target)

More on the same topics