Description
Solutions
Find Max Distinct Items 🍏
🔥 FULLTIME

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 Description

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

Example 1: 

Input:  n = 10, arr = [1, 3, 8], k = 10
Output: 5 
Explanation:

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: 

Input:  n = 5, arr = [3, 6], k = 8
Output: 5 
Explanation:

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
Thumbnail 0
Testcase
Result
Case 1

input:

output: