FastPrep
Problem · Array

Reduce Gifts

Learn this problem
● EasyAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

New Year's Day is around the corner and Amazon is having a sale. They have a list of items they are considering but they may need to remove some of them. Determine the minimum number of items to remove from an array of prices so that the sum of prices of any k items does not exceed a threshold.

Note: If the number of items in the list is less than k, then there is no need to remove any more items.

Function

reduceGifts(prices: int[], k: int, threshold: int) → int

Complete the function reduceGifts in the editor.

reduceGifts has the following parameters:

  • int prices[n]: the prices of each item
  • int k: the number of items to sum
  • int threshold: the maximum allowed price sum of k items

Returns

int: the minimum number of items to remove

Examples

Example 1

prices = [3, 2, 1, 4, 6, 5]k = 3threshold = 14return = 1
Example 1 illustration
The sum of prices for every k = 3 items must not be more than threshold = 14. The sum of the prices of the last three items is 6 + 5 + 4 = 15. The item priced $6 can be removed leaving: No 3 items' prices sum to greater than 14. Only 1 item needs to be removed.

Example 2

prices = [9, 6, 7, 2, 7, 2]k = 2threshold = 13return = 2
Items with prices 9 and 7 have a sum larger than 13. After removing these two items, prices' = [6, 2, 7, 2]. No k items have a sum of prices greater than threshold.

Example 3

prices = [9, 6, 3, 2, 9, 10, 10, 11]k = 4threshold = 1return = 5
Since no price is less than or equal to threshold, the sum of any k elements will always be greater than threshold. The threshold only applies to goups of k items. Now the goal is to reduce the arr length to k - 1 which requires the removal of 5 elements.

Constraints

  • 1 <= k <= n <= 105
  • 1 <= threshold <= 109
  • 1 <= prices[i] <= 109

More Amazon problems

drafts saved locally
public int reduceGifts(int[] prices, int k, int threshold) {
  // write your code here
}
prices[3, 2, 1, 4, 6, 5]
k3
threshold14
expected1
checking account