FINDMEEE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice

Contest

DIFFICULTY:

Easy

PREREQUISITES:

Strings, Set, Hashing, Sorting

PROBLEM:

Given a set of N strings with exactly 1 string occurring twice, find this string.

QUICK EXPLANATION:

Keep adding all the strings to a set and once you encounter a string which is already present in the set, that is the duplicate string.

EXPLANATION:

Subtask 1:

Write two nested loops to iterate over all possible pairs and find the duplicate string.

Time Complexity: \mathcal{O}(N^2) per test case

Subtask 2:

Keep adding all the strings to a set and once you encounter a string which is already present in the set, that is the duplicate string.

Time Complexity: \mathcal{O}(N log N) per test case

Alternative Solution: Add the strings to a vector and sort it. Now, the duplicate strings will be adjacent in this sorted vector.

SOLUTIONS:

Subtask 1 
#include <bits/stdc++.h>
using namespace std;

int main () {

    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        string name;
        vector<string> names;
        for (int i = 0; i < n; ++i) {
            cin >> name;
            names.push_back(name);
        }

        for (int i = 0; i < n; ++i) {
            bool done = false;
            for (int j = i + 1; j < n; ++j) {
                if (names[i] == names[j]) {
                    cout << names[i] << endl;
                    done = true;
                    break;
                }
            }
            if (done) {
                break;
            }
        }
    }
    return 0;
}
Complete Solution 
#include <bits/stdc++.h>
using namespace std;

int main () {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        string name;
        set<string> product_names;
        string duplicate;
        for (int i = 0; i < n; ++i) {
            cin >> name;
            if (product_names.find(name) != product_names.end()) {
                duplicate = name;
            }
            product_names.insert(name);
        }

        cout << duplicate << endl;
    }
    return 0;
}