if the majority occurs more than half of the size of the array, you can find that using 2 different solutions: 1- the majority is the median. So, in order to find the median, you can apply partitioning algorithm (used in QuickSort) The running time: O(logn) 2- Apply Moore’s Voting Algorithm: Running time: O(n) , space required: O(1) (the counter) ***************************************** If you do not know how many times the majority happens, you can use the below solutions: 1- Use a hash table a. (mod of the largest number (you can find the largest nr in O(logn) using partitioning algorithm). b. define a variable and call it max-major-count, max-major-nr b. Fill out all the cells by 0, then start hashing the numbers in your array. each time you hash to cell X increment its value by 1, and then compare it with max-major if the value is bigger than max-major, change max-major to that value. And change max-major-nr to the index of the cell (that would be that number. (run time of this part is: O(n)) Total running time: O(logn) +O(n) = O(n) Space required: O(n) + O(2) = O(n+2)