Michael is celebrating his 10th birthday and he wished to arrange a party for all his classmates. But there are n tough guys in his class who are weird. They thought that this is the best occasion for testing their friendship with him. They put up conditions before Michael that they will break the friendship unless he gives them a grand party on their chosen day. Formally, the ith friend will break his friendship if he does not receive a grand party on the dith day. Michael is not a lavish spender and can give at most one grand party daily. Also, he wants to invite only one person to a party. So he just wonders what the maximum number of friendships he can save is.Please help Michael with this difficult task.Input format :The first line will contain a single integer denoting n. Assume that the maximum value for n is 50.The second line will contain n space-separated integers where ith integer corresponds to the day dith as given in the problem.Refer to the sample input for formatting specifications.Output format :The output should print a single line corresponding to the maximum number of friendships Michael can save.Refer to the sample output for formatting specifications.Sample test cases :Input 1 :23 2Output 1 :2Input 2 :54 1 3 3 5Output 2 :4
Question
Michael is celebrating his 10th birthday and he wished to arrange a party for all his classmates. But there are n tough guys in his class who are weird. They thought that this is the best occasion for testing their friendship with him. They put up conditions before Michael that they will break the friendship unless he gives them a grand party on their chosen day. Formally, the ith friend will break his friendship if he does not receive a grand party on the dith day. Michael is not a lavish spender and can give at most one grand party daily. Also, he wants to invite only one person to a party. So he just wonders what the maximum number of friendships he can save is.Please help Michael with this difficult task.Input format :The first line will contain a single integer denoting n. Assume that the maximum value for n is 50.The second line will contain n space-separated integers where ith integer corresponds to the day dith as given in the problem.Refer to the sample input for formatting specifications.Output format :The output should print a single line corresponding to the maximum number of friendships Michael can save.Refer to the sample output for formatting specifications.Sample test cases :Input 1 :23 2Output 1 :2Input 2 :54 1 3 3 5Output 2 :4
Solution
This problem can be solved using a greedy algorithm and sorting. Here are the steps:
-
Parse the input. The first line gives the number of friends, n. The second line gives the days each friend wants to have a party.
-
Sort the days in descending order. This is because
Similar Questions
A man desires to throw a party for some of his friends. In how many ways can he select 7 friends from a group of 14 friends, if the two of his friends(say ’A’ and ’B’) will not attend the party together?
A person has 8 friends. The number of ways in which he may invite one or more of them toa dinner is.(a) 250 (b) 255 (c) 200 (d) none of these
A lady gives a dinner party for six guests. In how many ways they be selected from among 10 friends
The number of guests (a)/ invited to the party (b)/ are five hundred (c) No error (
At the farewell party of a certain class, having n students, if each student of the class gave one gift each to exactly k other students of the class, the number of students in the class who received at least one gift each cannot be less thank.k + 1.n – k.n – 1.
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.