in Algorithms edited by
558 views
2 votes
2 votes
You have an array A with n JPEG images 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.

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 logn ) algorithm to determine if A has a majority element.
in Algorithms edited by
558 views

4 Comments

edited by
Ankit look at the following algorithm. The algorithm is a little modulation of the above one but this will definitely work for any array

Suppse there are n JPEG images

STEP 0 - If n is odd choose any one image among the n images check whether it is an majority element or not by comparining it with every other images if yes then return it otherwise destroy the image.

STEP 1 - Create n/2 boxes

STEP 2- Now, number the images from 1 to n. Also number the boxes from 1 to n/2.

STEP 3- Place the image number (2i -1) and 2i  in the box number i

STEP 4- We create another array of images by picking the image number (2i-1) from the box i if image (2i-1) matches with image 2i.

STEP 5- Recurse the STEPS 1 to 4 until there is no image to pick or we have only one image in the array.

STEP 6 - If there is no image to pick then return "the array do not have any majority element"

STEP 7 - If we have only one image then check it whether it is a majority element or not by comparing it with all the other images of the initial array. Return the image if it is a majority element otherwise return "There is no majority element in the array"

Check the above algo tell me if you find some flaw.
1
1
Ankit pls look at the above algorithm and tell me if there is any wrong.
0
0
bro , I m not getting ur algo.. if possible then please explain with a small example . and it is not divide and conquer ..right ?
0
0

Please log in or register to answer this question.

Related questions