CODEWITHSUNDEEP
c#arraysalgorithm
Muneeb Zulfiqar
Muneeb Zulfiqar

Reputation: 1023

Find duplicate in Array with single loop

The question is there is and unsorted array and the maximum value should be smaller than the length. I have to find the duplicate record in the array. The condition is to use a loop only once. This is what i have achieved so far. I wanted to know if there was any other approach through which i can achieve this.

int[] Arr = { 9, 5, 6, 3, 8, 2, 5, 1, 7, 4 };
int[] Arr2 = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
for (int i = 0; i < Arr.Length; i++)
{
    if (Arr2[Arr[i]] == 0)
    {
        Arr2[Arr[i]] = Arr[i];
    }
    else
    {
        Console.WriteLine("duclicate found");
    }       
}

Upvotes: 6

Views: 21903

Answers (6)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186668

Use any Set implementation, say HashSet<T>, e.g.

HashSet<int> hs = new HashSet<int>();
int[] Arr = { 9, 5, 6, 3, 8, 2, 5, 1, 7, 4 };

foreach (item in Arr) 
  if (hs.Contains(item)) {
    Console.WriteLine("duplicate found");
    // break; // <- uncomment this if you want one message only
  }
  else 
    hs.Add(item);

Edit: since hs.Add returns bool a shorter and more efficient code can be put:

HashSet<int> hs = new HashSet<int>();
int[] Arr = { 9, 5, 6, 3, 8, 2, 5, 1, 7, 4 };

foreach (item in Arr) 
  if (!hs.Add(item)) {
    Console.WriteLine("duplicate found");
    // break; // <- uncomment this if you want one message only
  }

Upvotes: 10

Sourav &#39;Abhi&#39; Mitra
Sourav &#39;Abhi&#39; Mitra

Reputation: 2520

Since you have this condition :

The question is there is and unsorted array and the maximum value should be smaller than the length.

Also assuming only positive numbers, which in your example applies

This can be done using O(n) time and O(1) space without using any LINQ, Dictionary, Hashing etc.

int[] arr = { 9, 5, 6, 3, 8, 2, 5, 1, 7, 4 };
for (int i = 0; i < arr.Length; i++)
{
     if (arr[Math.Abs(arr[i])] >= 0)
         arr[Math.Abs(arr[i])] = -arr[Math.Abs(arr[i])];
     else
         Console.WriteLine("Duplicate found " + Math.Abs(arr[i]).ToString() + "\n");
}

Upvotes: 3

HackerMan
HackerMan

Reputation: 914

try this code using LINQ

    int[] listOfItems = new[] { 4, 2, 3, 1, 6, 4, 3 };
var duplicates = listOfItems
    .GroupBy(i => i)
    .Where(g => g.Count() > 1)
    .Select(g => g.Key);
foreach (var d in duplicates)
    Console.WriteLine("The duplicate is "+d);

Upvotes: 0

Aseem Goyal
Aseem Goyal

Reputation: 2723

This will work if only array a[] contains numbers in range [0,n-1] {as in your question} and n is not very large to avoid integer range overflow . 

for(i=0;i<n;i++)
{
    if(a[a[i]%n]>=n)
         **duplicate is a[i]** !
    else   
    a[a[i]%n]+=n;

}

Time complexity : O(N)
Space complexity : O(1) !

Upvotes: 0

aevitas
aevitas

Reputation: 3833

The fastest way to obtain all duplicates, using LINQ, is this:

var duplicates = Arr.GroupBy(s => s).SelectMany(d => d.Skip(1));

This will return an IEnumerable of all duplicate elements in Arr, and you can use the following check to contain if there were any duplicates:

if (duplicates.Any())
{
    // We have a duplicate!
}

Upvotes: 0

amit
amit

Reputation: 178431

This is the Element Distinctness Problem.

This problem cannot be solved strictly linearly without additional space.

The two common approaches to solve the problem are:

  1. Using a HashSet - populate it while iterating and abort if you find a match - O(n) time on average and O(n) space
  2. Sort and iterate, after the array is sorted, duplicates will be adjacent to each other and easy to detect. This is O(nlogn) time and very little extra space.

Upvotes: 2

Related Questions