558 views
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.

edited
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.
Ankit pls look at the above algorithm and tell me if there is any wrong.
bro , I m not getting ur algo.. if possible then please explain with a small example . and it is not divide and conquer ..right ?

1
703 views