What are the properties of an array that affect time complexity? Usually we're talking about the size of the array, N, such that linear time operations, O(N), are those that perform an operation on each of the elements in the array. However, an important thing to consider is that you can evaluate N (the size of the array) itself in constant time. The only way this can be done in constant time is if the input satisfies the precondition that "1..n" means there are no *missing* values in that range. In other words, such an array from "1..5" must contain at least one instance of the numbers 1, 2, 3, 4, and 5. With that precondition, you know that the length of the array will be 5 if no duplicates and greater than 5 if it does contain duplicates.

SUM(array) - (N(N+1)/2) = missing number.

^^ Sorry, that's linear time *and* at best linear space, you fail.

I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers

This cannot be done in linear time unless the data-structure used to hold the integers has a property that immediately flags duplicates upon insertion. For e.g. like in a Dictionary/HashMap.

Obviously this can't be done with constant time or space. At best you could compute a solution in linear time. memoize/cache it once then you could return the solution in O(1) time for subsequent calls.

I attach pseudo code here: FindDuplicate(A) i = A.length j = 1 count = 0 while j < i if A[--j] - j == 0 j++ else count++ return count count holds the number of duplicated items

I think they are just asking to determine if there is any duplicate number ir not. Its not mentioned to find out which number it is. So that we can find out by using sum of n numbers

They asked for constant time. So checking sum will not work. For zero indexed arrays, Check if arr[len(arr)-1] == len(arr) - 1.

@Facebook Intern: That wont help .. In case there are 2 duplicates this can be broken. {1, 1, 4, 4}

I've seen this question posted several places as "Find if an array has duplicates, in constant O(1) space" but no restriction on time. If the array is not sorted, and there is no restriction on the actual values in each item, then there is no O(1) space and O(1) algo. if you sort the array, then you lose O(1) time and obviously can not detect duplicates even in a sorted array in constant time. If its like most other versions of this question, and its only O(1) space, then you could store the duplicate value in the array itself, overwriting earlier elements that you already scanned. You'd only need an index that points just past the last duplicate value written. But this is not constant time.

Correct answer is to place each value in the array in its corresponding index (i.e. if array[x] = 3, put 3 into array[3]). If an index already contains its corresponding value, there's a duplicate.