top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

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

+3 votes
124 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 Google+ Share Button LinkedIn Share Button Multiple Social 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
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...