Pages

July 19, 2018

#Algorithm: Detect duplicate elements in Array


How to detect duplicate elements in Array in Java?
1). Brute Force: In this approach we will compare each element of Array to all other elements and returns true if it founds duplicates. FYI, this is not an efficient choice.

2). Using HashSet: If you just need to find if whther the array has duplicates of not, convert that array into Set. Since Set doesn’t allow duplicates, the size of the corresponding Set will be smaller than the original Array if Array contains duplicates otherwise the size of both Array and Set will be the same.

If you need to find the duplicate element as well, then we can use add method. The add(Object obj) method of Set returns false if Set already contains an element to be added. We can use it to find out if the array contains duplicates in Java or not and also return the duplicate element.



In an integer array has 1 to 100 number, out of one is duplicate. How can you find the duplicate number?
We can simply add all numbers stored in an array, and the total sum should be equal to n(n+1)/2. To find the duplicate, we need to subtract actual sum to expected sum. The difference would give duplicate number (if present), else it will return 0.

We can also use brute force, but that will result in the performance of O(n^2) which is not good.

-K Himaanshu Shuklaa..

No comments:

Post a Comment