CareerCup

Try divide-and-conquer approach. Divide the whole set into 2 subsets of n/2 cards. The key observation is if there are more than n/2 cards that are equivalent, then one of the subset must contains more than n/4 equivalent cards. If we can determine the majority card, we can use it to test against the rest of the cards to get the answer.

Hi This is a classic "Majority Element Selection" problem. The Majority element selection algorithm is also discussed under some other thread in this website. I am repeating it for the sake of convenience:

Input: Array with n elements
int candidate=A[0];
int candidateindex=0;
int count=1;
for(int i=1; i<n;i++)
{
if(A[i]==candidate)
count++;
else if(count>1)
count--;
else
{
candidateindex=candidateindex+i;
count=1;
}
}

Output: A[candidateindex]

Explanation: Application of Divide and Conquer

Hi there,

I can't prove O(n), i can prove it to be 1/2 n^2.
mind to give some hints?

Wahoo

Say all elements which satisfy the problem in question are marked as 0 (all equivalent) and others as ci for card i, then consider this special case: 0|c1|0|c3|0|...|c(n-1)|0. ie. All elements at odd position are equivalent. We check for this condition by testing {c0,c2} followed by {c2,c4} if the test is successful!

Now if, we test {c0,c1}, {c2,c3}, ..., we get at least one pair which is equivalent. Say, we get k pairs (equivalent pairs). Only these k elements are candidates to satisfy the question.

-- if k is 1 and pair is {ci, c(i+1)}, we are done.( Test all other cards with ci)

-- if k > 1, then let ci represent {ci, c(i+1)}. Then, if there is a set of more than n/2 equivalent elements in the cards, then amongst the k representing cards of pairs at least k/2 are equivalent. (prove)
Thus the problem reduces to a smaller problem.

Continue pairwise checking, with special cases, till the solution is obtained.

its classic hash table. Use the accountNumber to hash all the cards. If you find the current location as non empty then you know there has alreay been a card with that number. Check for all that have the value 2...if that accounts for more than n/4 then u have more than n/2 duplicates....

1,2
3,4,5,6,9,10,12
7,8,11

how do you solve it?

a O(nlogn) solution

find(set, n/2);

find(set, n)
1. if set.size == 1 and n < set.size then answer yes
2. randomly select a card in the set, C
3. partition the cards into two sets, setL = cards equivalent to C and setR = cards not equivalent to C.
4. if (size of setL == n/2) then answer is yes
if (size of setL > N/2) find (setL, n);
else find(setR, n-setL.size())

Mathhhhh

Mohan's solution can't apply to the following:

2 2 3 3 2 2 3 4 3 5

2 should be returned, however, according to Mohan's soln, candidateindex is out of bound

http://geeksforgeeks.org/?p=503

http://geeksforgeeks.org/?p=503