You are viewing a single comment's thread. Return to all comments →
Even cheaper than a hash map (but still basically a hashmap) would be to use a simple integer array. Costs are limited to 10000. So create an array, indexed by cost, which stores the flavor id. With Java, this is pre-initialized to zero. For each flavor, see if the matching flavor is in the array: arr[m-newCost] != 0.
If it's there, the match is found. If not, store this item in the array.
Even though there is only 1 unique solution, you have to continue reading until the input for the "trip" is completed.
Integer array indexed by cost?
What if there are two flavors with the same cost. How would you resolve that using an array?
the value of array[cost] would represent how many duplicates are in your set.