Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
Homework answers / question archive / Letty is hired as a Sales Executive and her role is to sell items which are given to her in a bag
Letty is hired as a Sales Executive and her role is to sell items which are given to her in a bag. The bag contains n items where each item has an associated ID. Letty is inherently lazy and plans to delete a few items from her bag, but if she deletes more than m items, her mischief will be easily discovered. She also knows that selling like items makes her task simpler, so she wants her bag to contain as few different IDs as possible. Determine the minimum number of different IDs the final bag can contain if she can perform at most m deletions.
For example, she has a bag with n = 6 items, ids = [1, 1, 1, 2, 3, 2], and the maximum number of items she can delete is m = 2. Two possible actions are delete two items with ID = 2 or one with ID = 2 and one with ID = 3. Either way she will have 2 item IDs in the final bag: either ids = [1, 1, 1, 3] or ids = [1, 1, 1, 2].
Function Description
Complete the function deleteProducts in the editor below. The function must return an integer that represents the minimum number of item IDs in her bag after at most m deletions.
deleteProducts has the following parameters:
ids[ids[0],...ids[n-1]]: an array of integers
m: an integer
Constraints
1 ≤ n ≤ 100000
1 ≤ ids[i] ≤ 1000000
1 ≤ m ≤ 10000
Input Format For Custom Testing
The first line contains an integer, n, that denotes the number of elements in ids.
Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer that describes ids[i].
The next line contains an integer, m, that denotes the maximum number of items that can be deleted.
Sample Case 0
Sample Input For Custom Testing
4
1
1
1
1
2
Sample Output
1
Explanation
The bag contains 4 items of the same kind. Whichever item Letty deletes, she will have items of only ID = 1.
Sample Case 1
Sample Input For Custom Testing
6
1
2
3
1
2
2
3
Sample Output
1
Explanation
At most m = 3 items can be deleted from ids = [1, 2, 3, 1, 2, 2]. It is optimal to choose the items having IDs 1 or 3, leaving 3 items with ID = 2.
Required function
def deleteProducts(ids,m):
# Creating an empty dictionary
freq = {} #to count frequency of iids
for item in ids:
if (item in freq):
freq[item] += 1
else:
freq[item] = 1
sortedfreq = sorted(freq.items(), key=lambda x: x[1], reverse=False) #ids are sorted based repetitions
uniqueids=len(sortedfreq) # no of unique ids
delete=0
for i in sortedfreq:
if i[1]<=m:
delete=delete+1
m=m-i[1]
else:
break
return uniqueids-delete
Whole program:
from numpy import array
def deleteProducts(ids,m):
# Creating an empty dictionary
freq = {} #to count frequency of iids
for item in ids:
if (item in freq):
freq[item] += 1
else:
freq[item] = 1
sortedfreq = sorted(freq.items(), key=lambda x: x[1], reverse=False) #ids are sorted based repitions
uniqueids=len(sortedfreq) # no of unique ids
delete=0
for i in sortedfreq:
if i[1]<=m:
delete=delete+1
m=m-i[1]
else:
break
return uniqueids-delete
# Driver function
if __name__ == "__main__":
my_list =array([1, 1, 1, 2, 3, 2])
m=2
print(deleteProducts(my_list,m))
