9

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?

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
Namir M
  • 167
  • 1
  • 3

5 Answers5

19

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.

John Dvorak
  • 26,799
  • 13
  • 69
  • 83
  • But dont you have to compare each item with every other item for this? – smk Feb 07 '13 at 21:33
  • @SajitKunnumkal why would you? Every decent equality is transitive, and the problem is not well defined for non-transitive or asymmetric "equalities". – John Dvorak Feb 07 '13 at 21:36
  • Ok, so from what I understand: I will start with the first credit card number, if isSamePerson(currentCardNumber, nextCardNumber) returns True, I will increment a global counter. If they don't match, I will decrement this counter. If counter becomes zero, I will change the credit card number to the next candidate and continue like that. At the end, the credit card in the current value will be the majority one (iff we already know that there is a major credit card). Is that thinking correct? – Namir M Feb 07 '13 at 21:37
  • @NamirM correct. You might still want to check there _is_ a majority. – John Dvorak Feb 07 '13 at 21:38
  • 1
    @NamirM but you do not have majority credit cards, you have majority *owners* – Miquel Feb 08 '13 at 07:47
3

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

Note that since more than half of them belong to same person, if you consider two adjacent numbers, at least one pair of them are going to belong to same person.

If you consider all pairs (x1,x2), (x3,x4)...., and consider the subset of pairs where both elements belong to same person, a majority of same-person-pairs belong to the person who has majority of cards in first place. So, for every same-person-pair keep one of the card numbers and for non-same-person-pairs discard both. Do this recursively and return the last remaining same-person-pair.

You need to perform at most n comparisons.

NOTE: If n is odd keep the unpaired number.

Why this works: consider a case where n is even and person A owns n/2 + 1 cards. In the worst case you have exactly one pair where both cards are owned by A. In that case none of the other pairs are owned by same person ( other pairs contain one card of A and a card by other person).

Now, to create one matching pair of B (non-A person), you have to create one pair of B also. Therefore, at every instance a majority of matching pairs are owned by A.

ElKamina
  • 7,747
  • 28
  • 43
2

I don't have reputation to comment. The method told by Jan Dvorak is known as Moore's Voting Algorithm (Stream Counting Algorithm). Here's the code.

int majorityElement(int* nums, int numsSize) {
int count =0, i, majorityElement;
/*Moore's 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;}
HoneyBeer
  • 432
  • 6
  • 14
0

The question is to find out the majority element in an array. I shall use Boyer-Moore Majority Vote algorithm. I am doing this using HashMap.

public class majorityElement1 {
public static void main(String[] args) {
    int a[] = {2,2,2,2,5,5,2,3,3,3,3,3,3,33,3};
    fix(a);

}

public static void fix(int[] a ) {
 Map<Integer,Integer> map = new HashMap<>();

 for(int i = 0 ; i<a.length ; i++) {
     int r  = a[i];
     if(!map.containsKey(r)) {
         map.put(r, 1);
     }else {

         if(map.get(r) +1 >= a.length/2) {
             System.out.println("majority element => "+ r);
             return ;
             }else {
                 map.put(r,map.get(r) +1);
             }

     }//else1
 }//for
    }
}

The output is 3.

Soudipta Dutta
  • 1,353
  • 1
  • 12
  • 7
-1

DONE IN ONE PASS :

  • Start from the the second index of array let say i=1 initially.
  • Initially count=1.
  • Call isSamePerson(a[i],a[i-1]) where array a[] contains credit card numbers.
  • If the returned value is positive , do count++ and i++
  • else if returned value is 0 and count==1 , i++
  • else if returned value is 0 and count>1 , do count-- and i++
  • If i!=(n-1) , go to step 3 where n is number of cards.
  • else If at the end of array count>1 , then there are more than half of cards belonging to a single person
  • else there is no clear majority of over 50%.

I hope that this is understandable and writing code would be an easy thing.

TIME COMPLEXITY - O(N)
NUMBER OF API CALLS = N-1
SPACE COMPLEXITY - O(1)

kavish
  • 36
  • 6
  • 1
    I don't see how this would work. Suppose you had an array where the following was true: {person1, person2, person1, person3, person1} Wouldn't your algorithm return no majority? – Tanvir Ahmed Feb 28 '13 at 21:19
  • These kind of algorithms have to be proven mathematically. The fact that once the counter is bumped to 1 it will stay 1 or above is weird to me. For this input data `(1 1 2 1 1 2)` I don't think the algorithm would work. – egdmitry May 21 '14 at 17:27
  • This works on (1 1 2 1 1 2). Stepping though it: i starts a 1, count as 1. data [0 1] is 1 1, increment count and i. Now count:2, i:2. Data [1 2] is 1 2. Dec count, now inc i. count:1, i:3. data[2 3] = 2 1; now count:1 i:4. Data[3 4] is 1 1. Now count:2, i:5. i now =n-1, so halt. count is 2, there is a majority answer. But we don't know which, yet. – David Siegel Oct 11 '16 at 00:13