CODEWITHSUNDEEP
arraysalgorithm
Ravi Gupta
Ravi Gupta

Reputation: 6480

Find duplicate element in an array in O(log n) time

I know that similar questions might be asked a number of time but it is different from those.

Given an unsorted integer array with values 1 to N-1 has one duplicate element in it (N is the size of the array and max value is N-1 because of the duplicate element). What is the best way to find the duplicate element? If possible O(log n).`

I know the O(n) solution but is there any way to do this problem in O(log n) time?

O(n) solution:

1) Find sum of first N-1 natural numbers using N(N-1)/2, lets say it SUM1
2) Find sum of all the elements of the arrays, let say it SUM2

Duplicate = SUM2 - SUM1

Upvotes: 0

Views: 3404

Answers (2)

coder
coder

Reputation: 65

It cannot be done in sub-linear time. The input has no such property (like sorted array) to let you do it in log(N) time.

Upvotes: 1

amit
amit

Reputation: 178521

It cannot be done sub-linearly, the array is unsorted, so you need to read all elements at worst case.

This intuition is pretty generic and holds for many algorithms dealing with unsorted arrays, since your dupe element can be awaiting "behind the bound" you have.

The same intuition does not apply for questions with sorted arrays, of course.

Upvotes: 7

Related Questions