AITC2G13 - Editorial

PROBLEM LINK:

Practice

Contest Link:

Setter: Rahul Kumar

Tester: Rahul Kumar

Editorialist: Anushwar Sharma

DIFFICULTY:

Simple

PREREQUISITES:

Basic observations, Array, Maps.

PROBLEM:

Chef has a box of N chocolates with different flavours A_1,A_2,A_3 up to A_N , where A_i denotes the flavour of i^{th} chocolate. Chef considers a flavor of chocolate good if there is only one chocolate of that flavor in the box.
Chef wants to know, how many good flavors of chocolates are there in the box.

EXPLANATION

We have to find the numbers which occur only once.
One method is to use a map index as an element and map value as an occurrence. We increase the value of elements every time on the map. Then take an iterator pointing to the beginning of the map and run a loop till the end. We check if the second value of the map is one then add one to the ans.
There are more ways to solve this question but this solution is best with time complexity O(n).

SOLUTION:

Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define vi vector<int>
#define w(x) int x; cin>>x; while(x--)
#define pb push_back 

int32_t main() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif   
    fio
    int T;
    cin>>T;
    while(T--)
    {
        int n,x,s=0;
        cin>>n; map<int,int> m;
        for(int i=0;i<n;i++)
        {
            cin>>x;
            m[x]++;
        }
        for(auto i=m.begin();i!=m.end();i++)
        {
            if(i->second==1)
                s++;
        }
        cout<<s<<"\n";
    }
}

Note: If you are a beginner, don’t be scared of the few lines that have been written at the top. Just focus on the code starting from the variable declaration and if you don’t understand any shorthand terminology mentioned in the code, look at the top “#define”, where we have defined all the constants used in the code.

Feel free to share your approach, if you want to(even if it’s the same). Suggestions are welcomed as always had been. :slight_smile: