CareerCup

when array is not sorted, create an array (which will act like a hash map, index as key). If you get number for which the array[number] is already filled, you found a duplicate. Now, you can stop right there and using summation function for 1toN number, you can find missing number.
sum_of_n = (N (N+1))/2
i.e. missing_number = sum_of_n - (sum_of_array_elements - duplicate_number_found)

If array is sorted, traverse the array, if A[i] != i+1 then i is a duplicate number and again use above formula for missing number.

This can be done in O(n) time and constant space
1. for every element of array a[i] . if (a[abs(a[i])-1] > 0) a[abs(a[i])-1] = -1*a[abs(a[i])-1]
2. if (a[abs(a[i])-1] <0) it means abs(a[i]) is a duplicate element
3. To get the missing element, we can traverse the array again and find the only +ve element, lets say a[k] is +ve then k+1 is the missing element

E.g. say we have array 1,3,3,2
i = 0 a[1-1] is +ve so array would be {-1,3,3,2}
i = 1 a[3-1] is +ve so array would be {-1,3,-3,2}
i = 2 a[3-1] is -ve which means abs(a[2]) which is 3 is a duplicate element
i = 3 a[2-1] is +ve so array would be {-1,-3,-3,2}

Now the only +ve in this array is 2 i.e. k=3, hence the missing element is k+1 which is 4

This can be done in O(n) time and constant space
1. for every element of array a[i] . if (a[abs(a[i])-1] > 0) a[abs(a[i])-1] = -1*a[abs(a[i])-1]
2. if (a[abs(a[i])-1] <0) it means abs(a[i]) is a duplicate element
3. To get the missing element, we can traverse the array again and find the only +ve element, lets say a[k] is +ve then k+1 is the missing element

E.g. say we have array 1,3,3,2
i = 0 a[1-1] is +ve so array would be {-1,3,3,2}
i = 1 a[3-1] is +ve so array would be {-1,3,-3,2}
i = 2 a[3-1] is -ve which means abs(a[2]) which is 3 is a duplicate element
i = 3 a[2-1] is +ve so array would be {-1,-3,-3,2}

Now the only +ve in this array is 2 i.e. k=3, hence the missing element is k+1 which is 4

Using a bitset of size n, initialized to 0.
As you traverse the array, set the particular bit in the bitset. If you see any bit already set, that's the duplicate. To find the missing number, you will need to traverse the bitset, and any number set to 0 is the missing integer.
O(n) time and O(n) space...

If the array is sorted, then a single traversal will do... without needing a bitset... O(n) time and constant space..

Method 1:

For unsorted case, you can use bitset of JustCoding says, and is a good solution.

Method 2:

If you want O(1) space, then you can compute the XOR of the array with 1 to n. If the missing number is a, and repeated number is b, then you get a XOR b as the result, which will be non-zero. Pick one bit position p, and then do the XOR again, but consider two separate buckets: bucket 0 = numbers whose bit position p is 0, bucket 1 = numbers whose bit position p is 1. At the end, you will get the two numbers a and b. Make another pass, and find out which is which (if also you need to specify that).

Sorted case:

In the case of sorted, it might seem like a binary search might work, but i think we can prove that we need to look at atleast n/2 positions.

Suppose you didn't, then your algorithm misses two consecutive spots. Now an adversary can choose those two spots and make the missing and duplicated number to fit in those spots. All your algorithm gets information is the presence of n/2 elements.

In fact, we can achieve the n/2 bound in the sorted case.

Assume array is index 1...n.

Look at A[2]. If A[2] = 1, then 1 2 is missing. if A[2] > 2, then 1 is missing.
Now look at A[4] and so on.

I think Loler is the most dumb guy i have ever seen... so much explanation for such a bad solution...

can be solved using Mathematics.

public void findTwoNumbers(){
/*let duplicated number be x and missing number be y
sum the elements to n numbers sum =(n)(n+1)/2-x+y
since we know sum and n we get x-y
similarly sum the sqare of elements we get sq_sum=(n)(n+1)(2n+1)/6-x2+y2
from this we get x2-y2
we can get x and y from this
complexity o(n)

ex: 1,2,3,4,5,5,7
x-y = 1
x2-y2 = 11

x2 = 11 + y2
x = y + 1
(Y+1)2 = 11+y

y=5;
x=6;
*/

}