First time here? Checkout the FAQ!
+1 vote

You have an array $A$ with $n$ objects, some of which are identical. You can check if two objects are equal but you cannot compare them in any other way—i.e. you can check A[i] == A[j] and A[i] != A[j], but comparisons such as $A[i] < A[j]$ are not meaningful. (Imagine that the objects are JPEG images.) The array A is said to have a majority element if strictly more than half of its elements are equal to each other. Use divide and conquer to come up with an $O(n \log n)$ algorithm to determine if $A$ has a majority element.


asked in Algorithms by Veteran (87.2k points)   | 58 views

Please log in or register to answer this question.

Top Users Sep 2017
  1. Habibkhan

    6826 Points

  2. Arjun

    2310 Points

  3. Warrior

    2302 Points

  4. nikunj

    1980 Points

  5. A_i_$_h

    1842 Points

  6. manu00x

    1750 Points

  7. Bikram

    1744 Points

  8. SiddharthMahapatra

    1718 Points

  9. makhdoom ghaya

    1690 Points

  10. rishu_darkshadow

    1672 Points

26,033 questions
33,610 answers
31,066 users