1122MediumArrayTwo PointersBinary SearchSorting

Dies That Hold Against Each Press

Tracked in this browser only

Trains the technique from

LeetCode 2300Successful Pairs of Spells and Potions

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O((n + m) log m) for m dies ordered once and one search per press.Space O(m) for the ordered dies.

For a fixed press, the strength rises with the die's rating, so the dies that hold are exactly those from some rating upwards. Finding that threshold turns the count into a lookup rather than a scan. A press of force `f` needs a rating of at least `target` divided by `f`, rounded upwards, since ratings are whole numbers and a rating one below the true quotient would fall short. Rounding down instead would let through dies that do not reach the target. So order the dies once, and for each press find where its needed rating would slot into that order, taking the first position holding a rating at or above it. Everything from there to the end holds, so the count is the die total less that position. The threshold has to be included rather than skipped, because a rating landing exactly on it makes a stamp of exactly the target, which counts.

Pythonentry point: successful_pairs

def successful_pairs(presses, dies, target):
    from bisect import bisect_left
    order = sorted(dies)
    m = len(order)
    out = []
    for force in presses:
        need = (target + force - 1) // force
        out.append(m - bisect_left(order, need))
    return out

The obvious version

For each press, walk every die, multiply the two numbers and count the products reaching the target. Costs the press count times the die count.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_successful_pairs(presses, dies, target):
    out = []
    for force in presses:
        count = 0
        for rating in dies:
            if force * rating >= target:
                count += 1
        out.append(count)
    return out

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in