The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+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.

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4k
- Digital Logic 1.7k
- Programming & DS 3k
- Algorithms 2.6k
- Theory of Computation 3.2k
- Compiler Design 1.2k
- Databases 2.4k
- CO & Architecture 2.1k
- Computer Networks 2.4k
- Non GATE 819
- Others 1.1k
- Admissions 244
- Exam Queries 419
- Tier 1 Placement Questions 16
- Job Queries 39
- Projects 4

29,156 questions

36,980 answers

92,147 comments

34,822 users