Introduction
In this article, we will find the duplicate number in a limited range array of size n with elements between 1 and n-1.
Now let us understand the concept of finding duplicates with the help of an example.
For example, Input: { 1, 7, 8, 2, 7, 8} Output: The duplicate element in the array is 7, 8 Input: { 5, 8, 9, 2, 9, 5,3,6} Output: The duplicate element in the array is 9, 5 |
Approach: Using Hashing
As we know, a data structure that associates values with keys is known as a hash table. This calculates key indexes using a hash function. We can store the value at the proper location based on the Hash Table index.
Now that you've devised a concept, let's look at its algorithm and implementation:
Approach: Use unordered_map for hashing
Count the number of times each element appears, and the elements with a frequency greater than one are printed. Because the range of numbers is unknown, unordered_map is used.
Implementation in Java
/*Java program to find duplicates in the array given*/
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
public class Main
{
// Driver program
public static void main(String[] arg)
{
int array[] = {11, 10, 40, 11, 7, 9, 5, 40, 11};
int n = array.length;
printingDuplicates(array, n);
}
//finding and printing duplicates
private static void printingDuplicates(int[] array, int n)
{
Map<Integer,Integer> map = new HashMap<>();
int count = 0;
boolean dupl = false;
for(int i = 0; i < n; i++){
if(map.containsKey(array[i])){
count = map.get(array[i]);
map.put(array[i], count + 1);
}
else{
map.put(array[i], 1);
}
}
for(Entry<Integer,Integer> entry : map.entrySet())
{
/* if the frequency is greater than 1
printing the element */
if(entry.getValue() > 1){
System.out.print(entry.getKey()+ " ");
dupl = true;
}
}
// if no duplicates are present
if(!dupl){
System.out.println("-1");
}
}
}
Output
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// function duplicates to find and print
void Duplicates(int arry[], int n)
{
// using unordered_map to store frequencies
unordered_map<int, int> freqc;
for (int i=0; i<n; i++)
freqc[arry[i]]++;
bool dupl = false;
unordered_map<int, int>:: iterator itr;
for (itr=freqc.begin(); itr!=freqc.end(); itr++)
{
// if the frequency is more than 1 print element
if (itr->second > 1)
{
cout << itr->first << " ";
dupl = true;
}
}
//If duplicates are not present
if (dupl == false)
cout << "-1";
}
// to test the driver program
int main()
{
int arry[] = {7, 18, 10, 10, 7, 6, 11, 12, 11};
int n = sizeof(arry) / sizeof(arry[0]);
Duplicates(arry, n);
return 0;
}
Output
Implementation in Python3
To store a number as a key and its frequency as a value in Python, use a dictionary. Because the range of integers is unknown, a dictionary can be used.
# Python3 program for finding duplicates
# by using a dictionary approach.
def printingDuplicates(arry):
dict = {}
for elem in arry:
try:
dict[elem] += 1
except:
dict[elem] = 1
for itm in dict:
# if the frequency is greater than 1
# then printing the element
if(dict[itm] > 1):
print(itm, end=" ")
print("\n")
# Driver Code
if __name__ == "__main__":
list = [13, 13, 11, 6,
2, 6, 5, 12, 11]
printingDuplicates(list)
Output
Implementation in C#
/* C# program for finding the duplicates in given array*/
using System;
using System.Collections.Generic;
class findingDuplicates
{
// function for finding and printing duplicates
static void printingDuplicates(int[] arry, int n)
{
Dictionary<int,
int> map = new Dictionary<int,
int>();
int count = 0;
bool dupl = false;
for (int i = 0; i < n; i++)
{
if (map.ContainsKey(arry[i]))
{
count = map[arry[i]];
map[arry[i]]++;
}
else
map.Add(arry[i], 1);
}
foreach (KeyValuePair<int,
int> entry in map)
{
// if the frequency is greater than 1
// printing the element
if (entry.Value > 1)
Console.Write(entry.Key + " ");
dupl = true;
}
// if no duplicates found
if (!dupl)
Console.WriteLine("-1");
}
// Driver Code
public static void Main(String[] arg)
{
int[] arry = { 3, 4, 4, 7,
5, 4, 5, 1, 1 };
int n = arry.Length;
printingDuplicates(arry, n);
}
}
Output
The above solution has time complexity O(N) and auxiliary space is O(N)
You can also read about the Longest Consecutive Sequence.