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

View Allnum of num

12 Answers

▲

7

▼

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

▲

3

▼

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.

▲

5

▼

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

▲

0

▼

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

▲

0

▼

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

▲

0

▼

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.

* This post has been removed. Please see our Community Guidelines or Terms of Service for more information.*

▲

5

▼

If an array has elements from 1 to n the size of the array will be n, thus if the size of the array is greater than n, there must exist a duplicate.

▲

3

▼

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

▲

0

▼

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

▲

0

▼

They asked for constant time. So checking sum will not work.

For zero indexed arrays,

Check if arr[len(arr)-1] == len(arr) - 1.

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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.