CareerCup

I feel hashing is the simplest and the most efficient solution. What do you guyz think?

sum of n no - n(n+1)/2
sum of integer in an array - sum
Duplicate no is n - ((n(n+1)/2) - sum)

e.g 1,1,2,3,4
n is 5
sum of 5 no - 5(5+1)/2 = 15
sum of no 11
Duplicate no - 5 - (15 - 11)

use hashing

the first will not be applicable in : N = 0,1,2,3,4,5,5
Here the Sum of n no : 20
Sum of integer : 28
Subtract: 8

Here 8 does not have any resemblance here.

Partition the array in odd an even numbers. If there are more odd numbers than even, partition the odd numbers by the next bit and repeat. If there are more even numbers than odd, look up the duplicate in the even numbers partition.

It is similar to the selection algorithm because on average the numbers left after each iteration is about half, so the complexity is approx:

O(N/2 + N/4 + N/8 + ...) which is O(N)

C++ example for N == 8:

#include <algorithm> // for std::swap
#include <iostream>
using namespace std;

int partition(int* a, int N, int mask)
{
    int m = -1;
    for (int i = 0; i != N; ++i)
    {
        if (a[i] & mask)
        {
            swap(a[++m], a[i]);
        }
    }
    return m + 1;
}

template<int N>
int findDuplicate(int (&a)[N])
{
    int lower = 0, upper = N, mask = 1;
    for (; mask < N; mask <<= 1)
    {
        int i = partition(a + lower, upper, mask);
        if (i > (upper - lower) / 2)
        {
            upper = i;
        }
        else
        {
            lower = i;
        }
    }
    return a[lower];
}

int main()
{
    int a[] = { 2, 7, 6, 4, 5, 6, 3, 1 };
    cout << findDuplicate<8>(a) << endl;
    return 0;
}

Yes hashing is efficient solution with extra storage it can be done in O(n).
Another method would be to sort the numbers in increasing order and then check if a duplicate exists. Complexity: O(nlgn)

Sort the array and apply binary search

yup, hashing's the way to go if space is not an issue.By the way sorting doesn't work if the array is read only.

other than hashing sorting technique is d best way !!! and while sorting we can find the duplicate element ....so no need to travel the array onced more !!!

iterate through the array and add the number with the length. then iterate once again and the one greater than 2*n is the answer.

for( i =0 ; i <length; i++)
{
   if(a[i] > n)
   {
      return a[i]; // duplicate number
   }
   a[i]+=n;
}

XOR all the integers in the array, the result will the number which is a duplicate

for(int i=0;i<size;i++)

if(array[Math.abs(array[i])] > 0)	
            array[Math.abs(array[i])] = -array[Math.abs(array[i])];
      else
   	    System.out.print(Math.abs(array[i]) + " ");

for(int i=0;i<size;i++)
   if(array[Math.abs(array[i])] > 0)	
      array[Math.abs(array[i])] = -array[Math.abs(array[i])];
   else //this is a duplicate
      return Math.abs(array[i]);

for(int i=0;i<size;i++)
   if(array[Math.abs(array[i])] > 0)	
      array[Math.abs(array[i])] = -array[Math.abs(array[i])];
   else //this is a duplicate
      return Math.abs(array[i]);

for(int i=0;i<size;i++)
   if(array[Math.abs(array[i])] > 0)	
      array[Math.abs(array[i])] = -array[Math.abs(array[i])];
   else //this is a duplicate
      return Math.abs(array[i]);

One of the best approach using time O(n) and space O(n) can be done using hashing, we will keep inserting the array elements in the hash table and check that if the element is present in the hash table from before then it is a repeating element in the array and the element will be the final output

Implementation:

int findelement(int arr[], int n){
	unordered_set<int> s;
	for(int i = 0; i < n; i++){
		if(s.find(arr[i]) != s.end())
			return arr[i];
		s.insert(arr[i]);
	}
}