FastPrep
Problem · Greedy

Find Max Distinct Items 🍏

Learn this problem
● MediumIBMFULLTIMEOA
See IBM hiring insights

Problem statement

There is a list of items in the shopping cart, each having a cost associated with it.

There are n items, the cost of the ith item is i dollars and m items have already been bought represented in the array arr. Currently, there are k dollars, find the maximum number of distinct items one can have in total after purchasing any number of items from that money.

Function

findMaxDistinctItems(n: int, arr: int[], k: int) → int

Complete the function findMaxDistinctItems in the editor below. The function must return an integer denoting the maximum count of distinct items that can be purchased.

findMaxDistinctItems has the following parameter(s):

  1. 1. n: an integer denoting the number of items
  2. 2. arr[n]: an integer array denoting already purchased items
  3. 3. k: an integer denoting amount in dollars

Examples

Example 1

n = 10arr = [1, 3, 8]k = 10return = 5
Consider n = 10, m = 3, k = 10, arr = [1, 3, 8]. So, the task is to find the maximum number of distinct items which can be purchased out of 10 items with 10 dollars apart from items [1, 3, 8]. At max, 2 items can be purchased apart from the given 3. let's say item 2 and item 5. Total cost = 2 + 5 = 7 which is less than 10. Let us consider three items - Item 2, item 4, and Item 5. Total cost = 2 + 4 + 5 = 11 which is greater than 10. So, it is not possible. So, the answer is 5 (3 already purchased, and 2 purchased just now).

Example 2

n = 5arr = [3, 6]k = 8return = 5
At max, 3 items can be purchased apart from the given 2, let's say Item - 1, Item - 2, and Item - 4. Total cost = 1 + 2 + 4 = 7 which is less than 8. So, the answer is 5 (2 already purchased, and 3 purchased just now).

Constraints

  • 1 ≤ n ≤ 10^6
  • 1 ≤ m ≤ 10^5
  • 1 ≤ k ≤ 10^9
  • 1 ≤ a[i] ≤ 10^6

More IBM problems

drafts saved locally
public int findMaxDistinctItems(int n, int[] arr, int k) {
    // write your code here
}
n10
arr[1, 3, 8]
k10
expected5
checking account