The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
188 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?
asked in Algorithms by (41 points)
retagged by | 188 views

3 Answers

+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.
answered by Veteran (15.2k points)

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.
0 votes

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)

 

answered by Loyal (4.6k points)
0 votes
//Deleted

As I didn't see geeksforgeeks solution

I had mention about binary search algorithm
answered by (131 points)

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,100 questions
36,904 answers
91,826 comments
34,770 users