Practice

Contest

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:

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

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

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:

#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;
}