PROBLEM LINK:
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;
}