guys..sort the array using quicksort..and check adjacent
elements..u can know there are duplicates or
not..complexity-O(nlogn)+n-1

Get the summation. If it is not equal to (2N + 1)/2, you
surely have duplicates.

the formula given for summation shud be (n*(n+1))/2

but it will solve the problem only if we have one duplicate.
if we have many duplicates then we can still get the 
correct summation
for ex:
1 2 2 5 5

it has two duplicates but still total is 5*(5+1)/2=15

You can use intermediate step for count sort.

Take a new array B of size N, initialize all values to 0.
and then 
for each i from 1 to N,
if((++B[A[i]]) > 1) - there are duplicates.

--- Time complexity O(n)

#include<stdio.h>
void main()
{
int a[3],j,i,n;
clrscr();
printf("enter n");
scanf("%d",&n);
printf("enter els");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]==a[j])
printf("elements %d and %d are same",i+1,j+1);
}
}
}

We need not sort this array and we need save space.
{2, 4, 5, 1, 3} m=2;
{2, 2, 5, 1, 3} m=4;
{2, 2, 5, 4, 3} m=1;
{1, 2, 5, 4, 3} m=2;
--------------------
{1, 2, 5, 4, 3} m=5;
{1, 2, 5, 4, 5} m=3;
{1, 2, 3, 4, 5} m=5;
--------------------

I have tried it with c#. It is of O(2n)~O(n)
 public bool tellIfDuplicate(params int[] nums)
        {
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] != i + 1)
                {
                    int temp = nums[i];
                    nums[i] = nums[nums[i] - 1];
                    nums[nums[i] - 1] = temp;
                }
            }
            for(int i=0;i<nums.Length;i++)
                if(nums[i]!=i+1)
                    return true;
            return false;
        }

The following algorithm works. It is O(n) and no extra 
storage required
        public static bool HaveDuplicate(int[] nums)
        {
            for (int i = 0; i < nums.Length; i++)
            {
                int tmp = nums[i];
                if (tmp < 0)
                    tmp = -tmp;

                if (nums[tmp - 1] < 0)
                {
                    return true;
                }
                else
                {
                    nums[tmp - 1] = -nums[tmp - 1];
                }
            }
            return false;
        }
    }

When its given you are allowed to destroy the array..do
think in that direction..


Read the first element go to that position, read that
position and mark it zero.. keep doing so...

If at any place we find zero.. that means array contains
duplicate.

If you mark places with zero, you will lose the original
value in that place which, eventually, leads to errors...

Assume an array starting as: 1-5-5-...

After first step array would be: 1-0-5-...

You will get stuck at the second step since every element
that you marked with zero will lead to the position 0.

Converting to negative makes more sense...

hey scrubs, use a hash map

loop through array {
if(hash[x] == x] return true// is dupe
else hash.add(x,x);
}

max O(n)

@Michael

Moron you are using extra space there.that is obvious.using
extra space many tough problems can be solved.without extra
space tell some better methods.

just add as many n(length of array) to an index as much it
has duplicates i.e. if array has size 7 and no. 5 is written
3 times then add 7 three times.so that after first loop
completion, you can just take division (a[5-1]/7 in this
case.so u got 3.)


//array is a[]
//len=length of array


for(i=0;i<len;i++)
{
b=a[i]%len;
a[b-1]=a[b-1]+7;
}
	//printing output
for(i=0;i<len;i++)
{
cout<<i+1<<" occurs: "<<(a[i]/7)<<endl;
}

srry.....few mistakes in above soln.....


just add as many n(length of array) to an index as much it
has duplicates i.e. if array has size 7 and no. 5 is written
3 times then add 7 three times.so that after first loop
completion, you can just take division (a[5-1]/7 in this
case.so u got 3.also original data at a[5-1] cant be loss
bcoz u can just tak (a[5-1]%len) nd u get the original data)


//array is a[]
//len=length of array


for(i=0;i<len;i++)
{
b=a[i]%len;
a[b-1]=a[b-1]+len;
}
	//printing output
for(i=0;i<len;i++)
{
cout<<i+1<<" occurs: "<<(a[i]/len)<<endl;
}

If there are no duplicates, Sum of numbers should be equal
to (N(N+1))/2.

Otherwise, duplicate is present.

No duplicate:
------------

Say N = 5

{1,2,3,4,5}

5(6)/2 = 15

1+2+3+4+5 = 15

Therefore no duplicate.

Duplicate:
---------

{1,2,3,4,1} 

Sum = 11

which is not equal to 15 (N(N+1)/2)

Therefore duplicate present.