CODEWITHSUNDEEP
arrays
Alex_ban
Alex_ban

Reputation: 321

Find repeated number in an array of unique numbers

There is an array where except one number (say magic-number) all are unique. The magic-number repeats itself more than half times the size of the array. e.g. 2, 10, 10, 10, 3. Find the magic-number without using any extra-space and without sorting it. Now is there any method to do it in O(n).

Upvotes: 1

Views: 55

Answers (1)

Colin D
Colin D

Reputation: 5661

Check each element against its neighbors, if any are equal then you have found the number. O(N)

If the first test did not find the number, then you in the following situation:

10,2,10,3,10.

In this case, the first number in the array is the magic number. O(1)

Upvotes: 2

Related Questions