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

Question

I was looking at the following question from Glassdoor:

Given N credits cards, determine if more than half of them belong to the same person/owner. All you have is an array of the credit card numbers, and an api call like isSamePerson(num1, num2).

It is clear how to do it in O(n^2) but some commenters said it can be done in O(n) time. Is it even possible? I mean, if we have an array of credit card numbers where some numbers are repeated, then the claim 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 goes as follows:

If there is a majority of one item (here, a person), then if you pair together items that are not equal (in any order), this item will be left over.

• Start with an empty candidate slot
• For every item
  • If the candidate slot is empty (count = 0), place it there.
  • Else if it is equal to the item in the slot, increment its count.
  • Else decrement the count for that slot(pop one item).
• If there is nothing left on the candidate slot, there is no clear majority. Otherwise,
• Count the number of occurences of the candidate (second pass).
• If the number of occurences is more than 50%, declare it a winner,
• Else there is no majority.

Note this cannot be applied if the threshold is below 50% (but it should be possible to adapt to a threshold of 33%, 25%... by holding two, three... candidate slots and popping only a distinct triple, quadruple...).

This also apllies to the case of the credit cards: All you need to is compare two elements (persons) for equality (via the API call), and a counter that is able to accomodate the total number of elements.

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