Determine if more than half of the array repeats in a separate array

Question

I watched the following question from Glassdoor :

Considering cards N loans, determine whether more than half of them belong to one person / holder. All you have is an array of credit card numbers, as well as an api call like isSamePerson (num1, num2).

It’s clear how to do this in O (n ^ 2), but some commentators said that this can be done in O (n) time. Is it possible? I mean, if we have an array of credit card numbers where some numbers are repeated, then the requirement makes sense. However, we need to make an API call for each credit card number to see its owner.

What am I missing here?

Answer 1

The algorithm is as follows:

If there is a large part of one element (here, man), then if you connect elements that are not equal (in any order), this element will be left.

• Start with an empty time slot.
• For each item
  • If the candidate slot is empty (count = 0), put it there.
  • If it is equal to an element in the slot, increase its number.
  • Reduce the counter for this slot again (place one item).
• If there is nothing left in the candidate slot, there is no clear majority. Otherwise,
• Count the number of occurrences of the candidate (second pass).
• If the number of entries exceeds 50%, declare it the winner,
• Otherwise there is no majority.

Please note that this cannot be applied if the threshold value is below 50% (but it should be possible to adapt to the threshold of 33%, 25% ... by placing two, three ... potential slots and only separate triple, quadruple ... )

This also applies to the case with credit cards: all you need is comparing two elements (persons) for equality (via an API call) and a counter that can accommodate the total number of elements.

Difficulty of time: O(N)
Space complexity: O(1) + input API calls: up to 2N-1: once in each pass, there is no first call for the first element in the first pass.

Answer 2

Let x1, x2, ..., xn be credit card numbers.

Please note: since more than half of them belong to the same person, if you count two adjacent numbers, at least one pair of them will belong to the same person.

If you consider all pairs (x1, x2), (x3, x4) .... and consider a subset of pairs in which both elements belong to the same person, most pairs of the same person belong to the person who has the most cards in the first place. Thus, for each pair with the same face, hold one of the card numbers, and pairs of the same faces discard both. Do this recursively and return the last remaining pair with the same face.

You need to complete no more than n comparisons.

NOTE. If n is odd, keep an unpaired number.

Why it works: consider the case when n is even, and person A owns n / 2 + 1 cards. In the worst case scenario, you have exactly one pair in which both cards belong to A. In this case, none of the other pairs belongs to one person (the other pairs contain one card A and another person's card).

Now, to create one matching pair B (non-identity), you also need to create one pair B. Therefore, in all cases, most matching pairs belong to A.

Answer 3

I have no reputation for comment. The method described by Jan Dvorak is known as the Moore Voting Algorithm (Stream Counting Algorithm). Here is the code.

 int majorityElement(int* nums, int numsSize) { int count =0, i, majorityElement; /*Moore voting algorithm Order(n), Auxiliary space: Order(1)*/ /*step:1-To get candidate for the majority element*/ for(i=0; i < numsSize; i++) { if(count==0) majorityElement = nums[i]; if(nums[i]==majorityElement) count++; else count--; } /*Step:2- To check whether this candidate occurs max no. of times */ count =0; for(i=0; i<numsSize; i++) { if(nums[i]==majorityElement) count ++; } if(count>numsSize/2) /*It can only be applied for majority check */ return majorityElement; return -1;} 

Answer 4

DONE IN ONE PASS:

• Start with the second index of the array, first let's say i = 1.
• Initially count = 1.
• Call isSamePerson (a [i], a [i-1]), where array a [] contains credit card numbers.
• If the return value is positive do count ++ and i ++
• else if the return value is 0 and count == 1, i ++
• else if the return value is 0 and count> 1, do count-- and i ++
• If I! = (N-1), go to step 3, where n is the number of cards.
• else If at the end of the count> 1 array there are more than half of the cards owned by one person
• otherwise there is no clear majority of over 50%.

I hope this is clear and writing code would be easy.

TEMPORAL INTEGRITY - O (N)
NUMBER OF CALLS = N-1
SPATIAL COMPLEXITY - O (1)