retagged by
741 views
0 votes
0 votes
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?
retagged by

4 Answers

1 votes
1 votes
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.
0 votes
0 votes
//Deleted

As I didn't see geeksforgeeks solution

I had mention about binary search algorithm
0 votes
0 votes
#one of the algo i.e easy to implement#

Look here you can use hash map i.e HashMap<Integer,Integer> map=new HashMap(Integer,Integer).. as whenever you see new elements make that entry in hash map and intialize its count to 1...i.e map.put(arr[i],1) and next time when the same element is seen you can add 1 to the count by fetching its value i.e count=map.get(arr[i])+1...now check whether this count is greater than n/2 or not if yes print majority element found and return and if not than put this count value i.e map.put(arr[i],count)...so time complexity here is just O(n) as there would be just one for loop...and space complexity here would be O(n) due to hash map data structure

Related questions

3 votes
3 votes
3 answers
1
2 votes
2 votes
2 answers
3
1 votes
1 votes
0 answers
4
aka 53 asked Nov 21, 2017
2,518 views
T(n) = 2T(n/2) + log nBy substitution T(n) = 4T(n/4) + 2log n/2 + lognI got stucked here