i have an array with randomly placed numbers from 1 to 1000000 ,there is an integer duplicated in the array what is the easiest , perf. efficient way to find that value

I'd have to agree with ozo's and phoffric's suggestion if performance is truly critical. A bit array would have you only looping the array once to locate the duplicate. So in terms of runtime cost, you should be looking at O(n). Memory cost is, of course, greater because you'd be introducing a second array/vector to track duplicate values.

Again, if performance is paramount, then the LINQ and sorting suggestions will not be as performant. LINQ has a bit of overhead associated with it--that's on top of the overhead you introduce by creating the new anonymous objects in the GroupBy's and Select's. Sorting is a bit better on performance than LINQ would be, but you've still got the overhead of executing the sort. You can mitigate some of this by choosing the most-performant sort, but you'll still have some degree of overhead.

The dictionary approach is the bit array solution reimagined. It's easier to read, but it may not be as performant. You'd have to time it.

If performance is not critical, then the LINQ or dictionary solutions are good ways to go in terms of readability. These days, readability trumps performance save for a select few areas.

As a C# example of what ozo and phoffric suggest, you could use the BitArray class:

e.g.

using System;
using System.Collections;
using System.Diagnostics;

namespace ConsoleApplication34
{
    class Program
    {
        static void Main(string[] args)
        {
            const int MAX_VALUE = 1000000;
            BitArray vector = new BitArray(MAX_VALUE + 1, false);
            int[] array = SetupArray(MAX_VALUE);
            Stopwatch clock = Stopwatch.StartNew();

            for (int i = 0; i < array.Length; i++)
            {
                int value = array[i];

                if (vector[value])
                {
                    Console.WriteLine("Duplicate value: {0}", value);
                }
                else
                {
                    vector[value] = true;
                }
            }

            clock.Stop();

            Console.WriteLine("Elapsed MS: {0}", clock.ElapsedMilliseconds);

            System.Diagnostics.Debugger.Break();
        }

        static int[] SetupArray(int maxItems)
        {
            Random rand = new Random();
            int[] array = new int[maxItems];

            for (int i = 1; i < maxItems; i++)
            {
                rand.Next(rand.Next());
                array[i] = rand.Next(1, maxItems + 1);
            }

            return array;
        }
    }
}

Select all Open in new window

There's probably a way you can pull of the same with an array of integers and bit masking, but I don't know that it would be any more performant. That would be something you'd have to time.