Engines and Fuel

Medium

A test bench checks engines. The power of engine i is engines[i], and the quality of fuel batch j is fuels[j]. An engine and a fuel pass the test together if power times quality is at least threshold. Return an array as long as engines where position i holds how many fuel batches pass the test with engine i.

Example 1

engines=[2, 6, 1], fuels=[3, 1, 4, 2], threshold=8 → [1, 3, 0]

Engine 2 reaches 8 only with fuel 4. Engine 6 does it with 3, 4 and 2 (6 × 1 = 6 is too little). Engine 1 falls short with everything.

Example 2

engines=[5], fuels=[5, 5], threshold=25 → [2]

5 × 5 = 25 meets the threshold exactly, which counts. Both fuels work.

Constraints

1 ≤ len(engines), len(fuels) ≤ 10⁵
1 ≤ engines[i], fuels[j] ≤ 10⁵
1 ≤ threshold ≤ 10¹⁰

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Binary Search Sorting

Similar problems

Triples Under a Limit Medium Warm Every Cabin Medium Pairs With a Fixed Gap Medium Stick Triples That Form a Triangle Medium Nearest k Values Medium

Input

engines=[2, 6, 1], fuels=[3, 1, 4, 2], threshold=8

Expected

[1, 3, 0]

Run checks the first 3 tests in your browser. Submit checks all 86 tests on the server, hidden ones included.