134 views
Let an array A[1,....n] has n elements, and every element of an array is less than or equal to n. An element is said to be "majority element" if it is occurred in more than n/2 positions of an array. what is the time complexity to check whether the majority element exist or not?

+1 vote
Not exactly the array is said to be sorted here . My solution will take O(n) time but a O(n) space as well . The keys are less than n we can use a direct addressing table here . take an array of size n;
take the mod of all the element 1 by one and increment the array[element%n] which will take O(n) time. after the whole operation find the largest in O(n) . O(n) + O(n) time complexity.

If ans is O(n) with space O(n) then,

I think question should also mention that all elements are non-negative. right ?

I think It has stated that input array is 1 to n. That stand for positive number only.
I think, That is index of the array.

If the Given Array is Sorted than it is pretty easy
U can look into solution here

http://www.geeksforgeeks.org/check-for-majority-element-in-a-sorted-array/

If Not Sorted than there is Moore's Voting Algorithm Which can be Done in O(n)

//Deleted

As I didn't see geeksforgeeks solution