Given a generic array with ‘n’ items (not only integers). Give a solution for checking whether there are any duplicate elements in the array or not? You just need to return a boolean (true or false). State the complexity of your solution. Can you come up with another solution that has O(n logn) complexity? Explain.
i need the answer with generic array
The logic here is using a set. A set does not contain duplicate values. So now we insert all the elements that we are given in the array into the set.
So, if the array contains duplicates, then the set must have less number of elements than the array.
If the array has no duplicates, then the number of elements in the set will be equal to the number of elements in the array.
It is an O(n logn) solution, because we are inserting 'n' elements and each insertion has a complexity of O(log n).
The set makes use of a Binary Search Tree like implementation internally. So the complexity of insertion is O(log n).
I have given you a C++ code, if you want to test with your required type, then replace "type" with any of int, float, char or string or any other type as per your requirement.
Generic Code:
bool areDuplicatesPresent(vector<type> v){
set<type> s;
for(int i=0;i<v.size();i++){
s.insert(v[i]);
}
if(s.size() == v.size())
return false;
return true;
}
Testing with type as integer:
Code:
#include<bits/stdc++.h>
using namespace std;
bool areDuplicatesPresent(vector<int> v){
set<int> s;
for(int i=0;i<v.size();i++){
s.insert(v[i]);
}
if(s.size() == v.size())
return false;
return true;
}
int main(){
vector<int> v{1,2,3,4,5,5};
bool res = areDuplicatesPresent(v);
string ans;
if(res == true)
ans = "Yes";
else
ans = "No";
cout<<"Are there any duplicates in the array?
"<<ans<<endl;
}
Output:
Please appreciate the solution if you find it helpful.
If you have any doubts in the solution, feel free to ask me in the comment section.
Get Answers For Free
Most questions answered within 1 hours.