Registration System 4/C

Registration System

Intuition

From the constraints, the brute force approach can become too inefficient.

Checking all previous usernames for every new input will take:

O(n²)

With high constraints like 10^5, this approach will be inefficient.

Therefore, we require an approach that will help us:

Check whether the current username has been previously used.

Store the previously used usernames

This leads to the idea of using maps or hash tables.

Example:

bob

alice

bob

bob

Processing:

bob → new → Accepted

alice → new → Accepted

bob → exists → bob1

bob → exists → bob2

Approach

Use:

map<string, int>

For every username:

if it appears for the first time, print "OK"

else , print name + current frequency

Then increase the frequency.

  #include<bits/stdc++.h>
using namespace std;
    typedef  long long     ll;

  void solve();
int   main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
     #ifdef LOCAL
    cerr << "Execution time: " << 1000.f * clock() / CLOCKS_PER_SEC << " ms." << nl;
    #endif
    
        solve();
    return 0;       
}
void solve() {
    ll t;
    cin >> t;
  
    map<string, ll> nameo;
    for (int i = 0; i < t;i++){
        string s;
        cin >> s;
        if(nameo[s]==0){
            cout << "OK" << endl;
            nameo[s] = 1;
        }
        else{
            cout << s << nameo[s] << endl;
            nameo[s]++;
        }
    }
}

Complexity

O(n log n)

Using unordered_map, average complexity becomes:

O(n)