LAPTOPREC Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Jeevan Jyot Singh
Tester: Jakub Safin, Satyam
Editorialist: Pratiyush Mishra

DIFFICULTY:

1104

PREREQUISITES:

None

PROBLEM:

Chef wants to buy a new laptop. However, he is confused about which laptop to buy out of 10 different laptops. He asks his N friends for their recommendation. The i^{th} friend recommends the Chef to buy the ${A_i}^{th}laptop (1 \le A_i \le 10)$.

Chef will buy the laptop which is recommended by maximum number of friends. Determine which laptop Chef buys.
Print CONFUSED if there are multiple laptops having maximum number of recommendations.

EXPLANATION:

Here we can use an unordered map or an array of length 10 to keep count of number of recommendations for each laptop. Once we have the count, we can easily determine which laptop has the maximum recommendations which would be our answer.
Also we have to do one additional check to see if there are more than one laptop with maximum recommendations in which case the answer would be CONFUSED.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

3 Likes
2

Can someone please help , why this code is failing for the problem
n= int(input())
x=[]
dic1={}
while n>0:
m= int(input())
x=list(map(int,input().split()))[:m]
set1=set(x)
for i in set1:
dic1[i]=x.count(i)
val=dic1.values()
maxx=0
a=dic1.values()
maxx=max(a)

result=[]
for i in dic1.keys():
    if dic1[i]==maxx:
        result.append(i)
if len(result)>1:
    print("Confused")   
else: print(result[0])
n=n-1
3

hey apart from hashmaps i used simple array and count the no of duplicates but stuck in confuse part …can you help please

4

Hey. Can anybody tell me where the logic is going wrong. Couldn’t pass only one test case. In case of CONFUSED scenario, I am comparing last and second last elements in frequency arraylist and if they are equal, the it prints CONFUSED. Here is the code:

int N = scn.nextInt();
int[] arr = new int[N];

	    HashMap<Integer, Integer> map = new HashMap<>();
	    for (int i = 0; i < N; i++)
	    {
	        arr[i] = scn.nextInt();
	        int freq = map.getOrDefault(arr[i], 0);
	        map.put(arr[i], freq+1);
	        
	    }
	    if (arr.length == 1)
	   {
	    System.out.println(arr[0]);
	    continue;
	   }
	
   	int max_freq = 0;
	int maxele = arr[0];
	
	ArrayList<Integer> AL = new ArrayList<>();
	for (int i: map.keySet())
	{
	    int val = map.get(i);
	    if (val > max_freq)
	    {
	        max_freq = val;
	        maxele = i;
	    }
	    AL.add(val);
	}
	

   Collections.sort(AL);	
	if (AL.size() != 1 && AL.get(AL.size()-1) == AL.get(AL.size()-2))
	{
	    System.out.println("CONFUSED");
	}
	else
	{
	    System.out.println(maxele);
	}
	
	    
	   
	}
5

Simply count the mxm hash_value, if it is more than 1, just print confused.
You can refer my code to understand better :slight_smile:

void solve(){
    int no_of_friends;
    cin>>no_of_friends;
    int recommendation_arr[no_of_friends];
    int recomm_map[11]={0};
    for(int idx=0;idx<no_of_friends;idx++){
        cin>>recommendation_arr[idx];
        recomm_map[recommendation_arr[idx]]+=1;
    }
    int mxm_recomm=0,mxm=0;
    for(int idx=1;idx<11;idx++){
        if(recomm_map[idx]>mxm){
            mxm=recomm_map[idx];
            mxm_recomm=idx;
        }
    }
    int confused=0;
    for(int idx=1;idx<11;idx++){
        if(recomm_map[idx]==mxm)
            confused++;
    }
    if(confused>1)
        cout<<"CONFUSED\n";
    else
        cout<<mxm_recomm<<"\n";
}
6

Simply count the mxm hash_value instead of sorting hash_value, as it also takes O(nlogn) time for sorting map which is not feasible for this solution.
if mxm_hash_value more than 1, just print confused, else print mxm_hash_value index.
you can refer my code :

void solve(){
    int no_of_friends;
    cin>>no_of_friends;
    int recommendation_arr[no_of_friends];
    int recomm_map[11]={0};
    for(int idx=0;idx<no_of_friends;idx++){
        cin>>recommendation_arr[idx];
        recomm_map[recommendation_arr[idx]]+=1;
    }
    int mxm_recomm=0,mxm=0;
    for(int idx=1;idx<11;idx++){
        if(recomm_map[idx]>mxm){
            mxm=recomm_map[idx];
            mxm_recomm=idx;
        }
    }
    int confused=0;
    for(int idx=1;idx<11;idx++){
        if(recomm_map[idx]==mxm)
            confused++;
    }
    if(confused>1)
        cout<<"CONFUSED\n";
    else
        cout<<mxm_recomm<<"\n";
}
7

Hey! Thanks I got your logic and will try to implement it. But why is it failing on one test case? What is the mistake that I am making in this logic. If you can figure it out, it would be great.

8

Bro I don’t know much about java so i can’t understand the whole code properly.
can you give me that test case?

9

please help me with this code its working but passed only 1 test case

#include <bits/stdc++.h>

using namespace std;

int main()

{

int tc;

cin >> tc;

while (tc--)

{

    int n;

    cin >> n;

    vector<int> arr;

    for (int i = 0; i < n; i++)

    {

        int a;

        cin >> a;

        arr.push_back(a);

    }

    vector<int> nv(11, 0);

    for (int i = 0; i < n-1; i++)

    {

        nv[arr[i]]++;

    }

    sort(nv.begin(), nv.end());

    int count = 1;

    int index = arr[0];

    if (nv[10] != nv[9])

    {

        for (int i = 0; i < n; i++)

        {

            if (arr[i] == arr[i + 1])

            {

                count++;

                index = arr[i];

            }

        }

    }

    else

    {

        count = 0;

    }

    // cout<< count <<endl;

    // cout<<index<<endl;

    if (count == 0)

    {

        cout << "CONFUSED" << endl;

    }

    else

    {

        cout << index << endl;

    }

}

return 0;

}

10

Hey @kmukul_01 :smiling_face: ,
Your logic is correct but implementation is wrong for finding the maximum frequency value.
Here is your code I have modified.

#include <bits/stdc++.h>

using namespace std;

int main()

{

int tc;

cin >> tc;

while (tc--)

{

    int n;

    cin >> n;

    vector<int> arr;

    for (int i = 0; i < n; i++)

    {

        int a;

        cin >> a;

        arr.push_back(a);

    }

    vector<int> nv(11, 0);
    int maxfreq = 0;
    int val=0;
    for (int i = 0; i < n; i++)
    {
        nv[arr[i]]++;
        if(nv[arr[i]] > maxfreq)
        {
            maxfreq = nv[arr[i]];
            val = arr[i];
        }
    }

    sort(nv.begin(), nv.end());

    int count = 1;

    int index = arr[0];

    if ((nv[10] != nv[9]))
    {
        cout<<val<<"\n";
    }
    else 
    {
        cout<<"CONFUSED\n";
    }
}
return 0;
}
11

Hey @anubhav1112 :wave:

Thanks for asking your doubt.
you need to typecast the AL.get().

if (AL.size() != 1 && (int)AL.get(AL.size()-1) == (int)AL.get(AL.size()-2))
{
    System.out.println("CONFUSED");
}
else
{
    System.out.println(maxele);
}
12

Hey Prajjwal! Thanks for helping me out. Why is there a need to typecast though? The maximum possible value will surely fit in an int. I am little confused about it. It would be great if you could help again

13

hey @anubhav1112
There may be some internal error with arr. get() function that is why is advised to always typecast it.