Minimum Cost of Every K-Capable Model Set
Problem statement
You are given n models. Model i has a positive cost cost[i] and a two-character string featureAvailability[i]:
"00"supports neither feature."01"supports feature A only."10"supports feature B only."11"supports both features.
A set is k-capable when at least k selected models support A and at least k selected models support B. A model may be selected at most once. A "11" model counts toward both requirements.
Return an array of length n. At index k - 1, return the minimum total cost of a k-capable set, or -1 if no such set exists. Each value of k is a separate optimization; it does not consume models for later answers. Use a 64-bit integer result.
Function
minimumModelCosts(cost: int[], featureAvailability: String[]) → long[]Examples
Example 1
cost = [3,5,2,7,6]featureAvailability = ["10","11","01","00","11"]return = [5,10,16,-1,-1]Using 1-based model numbers, model 2 alone costs 5 and supports both features. Models 1, 2 and 3 cost 3 + 5 + 2 = 10 and support each feature twice. Models 1, 2, 3 and 5 cost 16 and support each feature three times. Only three models support each feature, so k = 4 and k = 5 are impossible. These results are recalculated from the listed arrays because the table in the original image is inconsistent.
Example 2
cost = [4,2,3]featureAvailability = ["11","01","10"]return = [4,9,-1]Model 1 alone costs 4 and meets k = 1; the two single-feature models would cost 5. For k = 2 all three models are required, costing 9. There are only two supporters of either feature, so k = 3 is impossible.
Constraints
1 <= cost.length <= 100000featureAvailability.length == cost.length1 <= cost[i] <= 1000000000featureAvailability[i].length == 2- Each feature string is one of 00, 01, 10, or 11.