6

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");
    }       
}
Improve this question
9
  • Use a set instead of second array. Before adding to the set, check if the set contains the element - if it does, you have a duplicate. Or you can just check the return value from Add - if it's false, the element is already present. Commented Apr 8, 2014 at 7:25
  • can you give me an example? Commented Apr 8, 2014 at 7:26
  • how is it different from the current the approach? Commented Apr 8, 2014 at 7:27
  • Never used C# before, but Set ≠ Array, in most programming languages a set means a HashSet, something that enforces a unique constraint on each of its elements. Commented Apr 8, 2014 at 7:30
  • 1
    Then your precondition ensures there must be duplication. Consider array of length 2, it could only be { 1, 1 }. Commented Apr 8, 2014 at 8:03

6 Answers 6

Reset to default
10

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
  }
Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

this is kind of the same approach? dont you think .
Yes your approach uses hash. But I would suggest keeping a bit array instead of int array to reduce memory cost.
@Muneeb Zulfiqar: It works with arbitrary integers, say "int[] Arr = { 5559, -2225, -56, 23, -56 };"
@Mohit Jain: No; the solution works with arbitrary integers, say "int[] Arr = { 5559, -2225, -56, 23, -56 };", that's why I'd rather not use bit array
@Dmitry Yes you are right. I was not talking about implementation but about the idea of hashing. Idea is essentially same. I would prefer your way of int sets so that my solution can run on complete range of ints. A set implemented using hash or BST. For such small memory when you are not using standard feature and implementing things by your own (possibly to learn, or array bounds are known), I suggested to prefer bitset.
|
3

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");
}
Improve this answer

Comments

2

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.
Improve this answer

5 Comments

the condition is to only loop once. how can you sort and compare in a single loop?
@MuneebZulfiqar foreach (var a in Arr.OrderBy(s => s))
OrderBy this loops more than once sir
@MuneebZulfiqar This answer aims to show you that not everything that we want can be done. This problem cannot be solved in a single loop without additional space, this should give you a hint you're on the right track.
@amit i had the same vision, i just needed some expert opinion :)
0

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!
}
Improve this answer

2 Comments

Linq cannot pe used. because it will violate the condition of using single loop.
@MuneebZulfiqar You're right, GroupBy actually loops three times just to sort. :)
0

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) !

Improve this answer

Comments

0

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);
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.