Find the majority element in array

by 
// returns -1 if there is no element that is the majority element, otherwise that element

// funda :: if there is a majority element in an array, say x, then it is okay to discard 
// a part of that array that has no majority element, the remaining array will still have
// x as the majority element

// worst case complexity :  O(n)

int findMajorityElement(int* arr, int size) { 
    int count = 0, i, majorityElement;
    for (i = 0; i < size; i++) {
        if (count == 0)
            majorityElement = arr[i];
        if (arr[i] == majorityElement) 
            count++;
        else
            count--;
    }
    count = 0;
    for (i = 0; i < size; i++)
        if (arr[i] == majorityElement)
            count++;
    if (count > size/2)
        return majorityElement;
    return -1;
}

More Related Contents:

  1. Maximum single-sell profit
  2. maximize the top element of the stack after performing exactly K operations
  3. Algorithm for all subsets of Array
  4. How do I check if an array includes a value in JavaScript?
  5. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  6. Finding three elements in an array whose sum is closest to a given number
  7. How to find the kth smallest element in the union of two sorted arrays?
  8. Algorithm to find k smallest numbers in array of n items
  9. How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate]
  10. Can min/max of moving window achieve in O(N)?
  11. Weighted random selection from array
  12. Print two-dimensional array in spiral order
  13. Find the Smallest Integer Not in a List
  14. How to find a duplicate element in an array of shuffled consecutive integers?
  15. How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?
  16. Given an array, find out the next smaller element for each element
  17. Binary Search algorithm implementations
  18. Algorithm to determine if array contains n…n+m?
  19. Find the 2nd largest element in an array with minimum number of comparisons
  20. Algorithm to rotate an array in linear time
  21. Find all subsets of length k in an array
  22. How to find max. and min. in array using minimum comparisons?
  23. Median of 5 sorted arrays
  24. Interview question: three arrays and O(N*N)
  25. How to find repeating sequence of characters in a given array?
  26. Maximum sum of non consecutive elements
  27. Finding kth smallest number from n sorted arrays
  28. calculating the number of “inversions” in a permutation
  29. Algorithm to apply permutation in constant memory space
  30. Find the first element in a sorted array that is greater than the target

Leave a Comment