top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Find Time Complexity, an element is repeating n/2 +1 times in a sorted array

+3 votes
372 views

In an "N" element integer sorted array, a particular elements is repeating "(N/2)+1" times. How much time it take to find the repeating element.

posted Oct 21, 2013 by Neeraj Mishra

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

1 Answer

+3 votes
 
Best answer

The time complexity is O(1).
Mid element of array is always repeated element.

Example : For even N.
N=4 Repeated element = N / 2 + 1 = 3
ARRAY 1,2,2,2
ARRAY 1 1 1 2

N=8 Repeated element = N / 2 + 1 = 5
ARRAY 1,2,2,4,4,4,4,4
ARRAY 1 2 2 2 2 2 4 5
ARRAY 2 2 2 2 2 3 4 5

Example : For Odd N.
N=3 Repeated element = N / 2 + 1 = 2
ARRAY 1,2,2,
ARRAY 1 1 2

N=7 Repeated element = N / 2 + 1 = 4
ARRAY 1,2,4,4,4,4, 5
ARRAY 2 2 2 2 3 4 5
ARRAY 2 3 3 3 3 4 5

answer Oct 21, 2013 by Vikas Upadhyay
...