GATE CSE
First time here? Checkout the FAQ!
x
0 votes
119 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)   | 119 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 (13.3k 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 (3.7k points)  
0 votes
//Deleted

As I didn't see geeksforgeeks solution

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

Related questions

0 votes
0 answers
2
+1 vote
3 answers
3
asked in Algorithms by radha gogia Boss (6.7k points)   | 212 views
Members at the site
Top Users Feb 2017
  1. Arjun

    4680 Points

  2. Bikram

    4004 Points

  3. Habibkhan

    3738 Points

  4. Aboveallplayer

    2966 Points

  5. sriv_shubham

    2278 Points

  6. Smriti012

    2212 Points

  7. Arnabi

    1814 Points

  8. Debashish Deka

    1788 Points

  9. sh!va

    1444 Points

  10. mcjoshi

    1444 Points

Monthly Topper: Rs. 500 gift card

20,788 questions
25,938 answers
59,533 comments
21,926 users