Question

Given a generic array with ‘n’ items (not only integers). Give a solution for checking whether...

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

Homework Answers

Answer #1

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.

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Write recursive method to return true if a given array of integers, named numbers, with n...
Write recursive method to return true if a given array of integers, named numbers, with n occupied positions is sorted in ascending (increasing) order, or returns false otherwise. Array can be empty or not. //PRECONDITION: Varible n denotes the number of occupied positions in the array and must be non-negative. Employee class has method getSalary() that returns employee's salary. // An empty array and an array with single element in it, are sorted. Method isSortedRec must be recursive and returns...
1.A stack implemented with an array has what performance? Select one: a. O(n3) b. O(n log...
1.A stack implemented with an array has what performance? Select one: a. O(n3) b. O(n log n) c. O(n) d. O(n2) 2. A stack uses the first in first out insertion and deletion method. Select one: True False 3. Match the following stack operations with their meaning. object pop(); boolean isEmpty(); push (object); integer size(); object top(); meanings are: - returns the number of elements stored -just removes the last inserted elements - returns the last inserted elements without removing...
Problem Definition: Problem: Given an array of integers find all pairs of integers, a and b,...
Problem Definition: Problem: Given an array of integers find all pairs of integers, a and b, where a – b is equal to a given number. For example, consider the following array and suppose we want to find all pairs of integers a and b where a – b = 3 A = [10, 4, 6, 16, 1, 6, 12, 13] Then your method should return the following pairs: 4, 1 15, 12 13, 10 A poor solution: There are...
We are given an array A of size n containing n positive and negative integers (the...
We are given an array A of size n containing n positive and negative integers (the array is indexed starting from 0). Our goal is to find two indices i and j such that 0 ≤ i ≤ j ≤ n and Pk=j k=i A[k] is maximized. Input sequence: [2, -4, 1, 9, -6, 7, -3] Output: [1, 9, -6, 7] or i = 2 and j = 5 Input sequence: [1, 2, 3, 4, 5, 6, -3] Output: [1,...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
Suppose that you want to add items to an array such that the items are always...
Suppose that you want to add items to an array such that the items are always ordered in ascending order; e.g., [1, 2, 2, 4, 5, 8, 9, 14, 32], and any duplicate values are adjacent to each other. We haven’t talked about sorting algorithms yet, so assume you want to be able to keep the items in the array in order without having to sort them. So for example, suppose you want to add the integer value 7 to...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm...
How to measure the time complexity of an algorithm? Identify an important operation in the algorithm that is executed most frequently. Express the number of times it is executed as a function of N. Convert this expression into the Big-O notation. A. For each of the three fragments of code, what is its worst-case time complexity, in the form "O(…)". (Use the given solution to the first problem as a model)                 //----------------- This is a sample problem – solved ------...
Coin Change Problem) Given a list of positive integers c[0...n − 1], and a positive integer...
Coin Change Problem) Given a list of positive integers c[0...n − 1], and a positive integer v, decides whether we can use numbers from c[0...n − 1] to make a sum of v, allowing any particular number in the list to be used multiple times. Or, mathematically, this means that there exists non-negative integer coefficients, x0, x1, ..., xn−1, such that v = x0c[0] + x1c[1] + ...xn−1c[n − 1]. For example, given c[0...3] = {2, 4, 6, 10}, and...
Complete the following function (detailed instructions are given below the code): private static int predecessor(int array[],...
Complete the following function (detailed instructions are given below the code): private static int predecessor(int array[], int arrayLen, int key) { // Complete this function. } Given a set of numbers, the predecessor of a number x is the highest number in the set that is less than or equal to x. Thus, if I have the set {6; 9; 10; 13; 22; 31; 34; 88}, then the predecessor of 31 is 31 itself, whereas the predecessor of 30 is...
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT