CareerCup

Here is an iterative version of the code to find the duplicate element. It works in O(log n) time -

int nums[] = { 1,2,3,4,5,6,7,7,8};
	int low = 0, high = 9;
	while(low<high){
		if( nums[ (low + high)/2 ] <= (low+high)/2 )
		 	high = (low + high)/2 -1 ;
		else
			low = (low + high) /2 + 1;
	}
        printf("The duplicate number is  : %d ", nums[low] );

As the array is sorted and as it srictly contains all numbers from 1 to n you can modify binary search to achieve O(logn) complexity. Because we can always expect the mid item in binary search. so if it is a hit, then the duplicate will be after this mid element, and if it is a miss the duplicate occurs before,

This could be done in O(log n) time.
Sample code:
-------------------

int find_sorted_duplicate(int* arr, int start, int end)
{
	if (start > end)
		return -1;
	int mid = (start + end)/2;
	if (arr[mid] == mid)
	{
		if (arr[mid-1] == arr[mid])
			return arr[mid];
		return find_sorted_duplicate(arr, start, mid);
	}
	else
	{
		if (arr[mid+1] == arr[mid])
			return arr[mid];
		return find_sorted_duplicate(arr, mid, end);
	}
}
Test cases:
---------------
int main()
{
        // Test case 1
        int arr[] = { 1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10};
	std::cout << find_sorted_duplicate(arr, 0, sizeof(arr)/sizeof(arr[0]) - 1) << std::endl;
        // Test case 2
        int arr1[] = { 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	std::cout << find_sorted_duplicate(arr1, 0, sizeof(arr1)/sizeof(arr1[0]) - 1) << std::endl;
        // Test case 3
        int arr2[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10};
	std::cout << find_sorted_duplicate(arr2, 0, sizeof(arr2)/sizeof(arr2[0]) - 1) << std::endl;
        return 0;
}

let say { 1,2,3,3}

here take the sum of all elements :9

and do (n*(n-1))/2 :n is 4 here 4*3 /2 = 6

9-6 is 3..3 is duplicate

O(log n) complexity...

if the given array is sorted O(log n) is possible, if it is not then O(n) by calculating the sum of the array and then subtracting from it, the sum of n numbers would give the answer

How about subtracting a[i] with a[i+1] as i moves from 0 to n.
The duplicate will be a[i] where a[i]-a[i+1] = zero.

Sum of natural numbers is n(n+1)/2.... if sum of array exceeds this then that is your answer

Going by the question, i assume that the array is already sorted and the interviewer doesn’t bother about the running time of the program(it is not mentioned).

Running time: Worst-case is linear O(n).

private function findDuplicate(a:Array):void {
for ( var i:Number = 1 ; i< a.length; i++ ){
if ( a[i] == a[i-1] ){
trace(“Duplicate number is: “ + a[i]);
break;
}
}

Pseudo Code:

1: Get sum of all the numbers in the array.
2: Get the duplicate by calculating totalSum - (sizeOfArray*(sizeOfArray+1)/2)

This is just a twin of binary search: Find the place that a[i] == a[i-1]. O(logn) for sure.

int nums[] = { 1,2,3,4,5,6,7,7,8};
int res = nums[0];
for (int i = 1; i < nums[].length; ++i)
res = res ^ i ^ nums[i];
return res;

Like a few others mentioned, it is as simple as summing up the numbers (from n+1) and then substracting the sum of n. The example in the question:

1 2 3 4 4 5 6 7 8 9 10 -> sum is 59
1..10 -> sum is 55

The difference is 4.