Devu has n friends. Each friend chooses a day and says:
“If you don’t give me a grand party on my chosen day, I’ll break the friendship.”
Devu is rich but frugal:
He can give at most one grand party per day.
He invites only one friend per party.
You must find: What is the maximum number of friendships he can save?
1. Problem Restatement
For each test case:
You’re given an integer n — number of friends.
You’re given n integers d_1, d_2, ..., d_n, where di is the day the i-th friend demands a party.
Devu can schedule at most one party per day, and each party is for exactly one friend.
He wants to satisfy as many friends as possible.
Goal: For each test case, compute the maximum number of friends whose requested day can be satisfied.
Input Format:
First line: Integer T — number of test cases.
For each test case:
First line: Integer n — number of friends.
Second line: n space-separated integers d_1, d_2, ..., d_n — demanded days.
Output Format:
For each test case, print a single integer — the maximum number of friendships Devu can save.
Constraints:
1 ≤ T ≤ 104
1 ≤ n ≤ 50
1 ≤ di ≤ 100
These constraints are small; even O(n2) would work per test case.
But we can do it more cleanly and efficiently in O(nlogn) or better.
Sample 1:
Input:
2
2
3 2
2
1 1
Output:
2
1
Explanation:
Test case 1:
Friends want days [3, 2].
Devu can give:
Day 2 → friend 2
Day 3 → friend 1
No day conflicts: he saves both friendships → answer 2.
Test case 2:
Both friends want day 1: [1, 1].
Devu can only hold one party per day.
So he can satisfy only one of them → answer 1.
2. Core Insight
Devu can give at most one party on any given day.
If multiple friends choose the same day, Devu can only satisfy one of them for that day.
Therefore, in each test case:
If a day appears k times among the di values, Devu can satisfy at most 1 of these k friends.
So the total maximum friendships saved is simply:
The number of distinct days among the n requested days.
3. Approach 1: Using Set / Unique Count (Optimized & Simple)
Idea:
Count how many distinct days are requested.
Each distinct day → Devu can host one party.
So the answer is just the size of the set of requested days.
Algorithm:
For each test case:
1. Read n.
2. Read the n integers for days.
3. Insert each day into a set (or boolean array since di≤100).
4. Let distinct_days = number of unique days in the set.
5. Print distinct_days.
Time & Space Complexity:
Let n be the number of friends in a test case.
Time:
Using a set: O(nlogn)
Using a boolean array: O(n)
Space:
O(D) where D≤100 (number of possible days), effectively constant.
Given constraints, both are very efficient.
4. Approach 2: Frequency Map (Basic View)
Another way to think:
Build a frequency map (day → count of friends).
For each day that appears at least once, Devu can save exactly 1 friendship.
So, answer = number of keys in the map.
This is effectively the same as counting distinct days but conceptually uses frequency.
Pseudocode (Distinct Days Approach):
6. C code
8. Python code
9. JavaScript code
Comments
Post a Comment