Given an array of n integers. The task is to print the duplicates in the given array. If there are no duplicates then print -1.
Examples:
Input : {2, 10, 100, 2, 10, 11}
Output : 2 10
Input : {5, 40, 1, 40, 100000, 1, 5, 1}
Output : 5 40 1
Note:The duplicate elements can be printed in any order.
Simple Approach: By using two loops. It has a time complexity of O(n2).
Efficient Approach: Use unordered_map for hashing. Count frequency of occurrence of each element and the elements with frequency more than 1 is printed. unordered_map is used as range of integers is not known. For Python, Use Dictionary to store number as key and it’s frequency as value. Dictionary can be used as range of integers is not known.
C++
// C++ program to find // duplicates in the given array #include <bits/stdc++.h> using namespace std; // function to find and print duplicates void printDuplicates(int arr[], int n) { // unordered_map to store frequencies unordered_map<int, int> freq; for (int i=0; i<n; i++) freq[arr[i]]++; bool dup = false; unordered_map<int, int>:: iterator itr; for (itr=freq.begin(); itr!=freq.end(); itr++) { // if frequency is more than 1 // print the element if (itr->second > 1) { cout << itr->first << " "; dup = true; } } // no duplicates present if (dup == false) cout << "-1"; } // Driver program to test above int main() { int arr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11}; int n = sizeof(arr) / sizeof(arr[0]); printDuplicates(arr, n); return 0; } |
Java
// Java program to find // duplicates in the given array import java.util.HashMap; import java.util.Map; import java.util.Map.Entry; public class FindDuplicatedInArray { // Driver program public static void main(String[] args) { int arr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11}; int n = arr.length; printDuplicates(arr, n); } // function to find and print duplicates private static void printDuplicates(int[] arr, int n) { Map<Integer,Integer> map = new HashMap<>(); int count = 0; boolean dup = false; for(int i = 0; i < n; i++){ if(map.containsKey(arr[i])){ count = map.get(arr[i]); map.put(arr[i], count + 1); } else{ map.put(arr[i], 1); } } for(Entry<Integer,Integer> entry : map.entrySet()) { // if frequency is more than 1 // print the element if(entry.getValue() > 1){ System.out.print(entry.getKey()+ " "); dup = true; } } // no duplicates present if(!dup){ System.out.println("-1"); } } } |
Python3
# Python 3 code to find duplicates # using dictionary approach. def printDuplicates(arr): dict = {} for ele in arr: try: dict[ele] += 1 except: dict[ele] = 1 for item in dict: # if frequency is more than 1 # print the element if(dict[item] > 1): print(item, end=" ") print("
") # Driver Code if __name__ == "__main__": list = [12, 11, 40, 12, 5, 6, 5, 12, 11] printDuplicates(list) # This code is contributed # by Sushil Bhile |
Output:
12 11 5
Time Complexity: O(n)
Related Post :
Print All Distinct Elements of a given integer array
Find duplicates in O(n) time and O(1) extra space | Set 1
Duplicates in an array in O(n) and by using O(1) extra space | Set-2
Print all the duplicates in the input string
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments