CODEWITHSUNDEEP
algorithmdata-structures
Namir M
Namir M

Reputation: 167

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

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?

Upvotes: 9

Views: 6821

Answers (5)

Soudipta Dutta
Soudipta Dutta

Reputation: 2132

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.

Upvotes: 0

HoneyBeer
HoneyBeer

Reputation: 442

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;}

Upvotes: 2

kavish
kavish

Reputation: 26

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)

Upvotes: -1

John Dvorak
John Dvorak

Reputation: 27287

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.

Upvotes: 19

ElKamina
ElKamina

Reputation: 7807

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.

Upvotes: 3

Related Questions