CareerCup

O(n) solution:
1) Find sum of first (N-1) natural numbers i.e (N(N-1))/2 : O(1) time
2) Find sum of all the elements of the array : O(n) time

Duplicate = Difference between Sum2 and Sum1

Algorithm:
1. Sum up all elements in the array
2. Say that the double value is x. We know that the sum of 1, 2, ..., n is ((1+n)/2)*n. Subtract the sum we calculated is 1 from this and we get: n-x. We know n, and so we know x.

keep on hashing every number before hashing any number check if it already exist . the duplicate will be found in O(n).

XOR all elements of array ^ (XOR 1 to N-1) = required number. Run time complexity is o(n) and space complexity is O(1).

XOR all elements of array ^ (XOR 1 to N-1) = required number. Run time complexity is o(n) and space complexity is O(1).

D = duplicate number
M = missing number
abs(D - M) = (n*(n + 1)) / 2 - (Sum of array elements)
abs(D + M) = ( (n*(n + 1)*(n + 2)) / 6 - (Sum of squares of array elements) ) / abs(D - M)

Solve the two equations.

D= duplicate number
M=missing number
abs(M-D)=(n*(n + 1)) / 2 - (Sum of array elements)
abs(M+D) = ( (n*(n + 1)*(2*n+1)) / 6 - (Sum of squares of array elements) ) / abs(M-D)

Ravi Gupta's solution is good.

1. Sum of all the array elements - sum of first N-1 elements

2. Second solution: Sum up all the array elements. then XOR the result with numbers from 1 to N-1. The resultant value is the duplicate element.

I have a different O(n) solution.
Say the array with duplicate element is called dup.
since our array has 1 to N-1 elements, declare a new array of size 'N' with all elements initialized to 0.

int a[N] with all elements initialized to 0.
for i = 0 to N
a[dup[i]]++

at the end only one position in a will have an index greater than 1 and that index will be the duplicate element