number which appears more than n/3 times in an array

Question

I have read this problem Find the most common entry in an array

and the answer from jon skeet is just mind blowing .. :)

Now I am trying to solve this problem find an element which occurs more than n/3 times in an array ..

I am pretty sure that we cannot apply the same method because there can be 2 such elements which will occur more than n/3 times and that gives false alarm of the count ..so is there any way we can tweak around jon skeet's answer to work for this ..?

Or is there any solution that will run in linear time ?

Answer 1

Jan Dvorak's answer is probably best:

• Start with two empty candidate slots and two counters set to 0.
• for each item:
  • if it is equal to either candidate, increment the corresponding count
  • else if there is an empty slot (i.e. a slot with count 0), put it in that slot and set the count to 1
  • else reduce both counters by 1

At the end, make a second pass over the array to check whether the candidates really do have the required count. This isn't allowed by the question you link to but I don't see how to avoid it for this modified version. If there is a value that occurs more than n/3 times then it will be in a slot, but you don't know which one it is.

If this modified version of the question guaranteed that there were two values with more than n/3 elements (in general, k-1 values with more than n/k) then we wouldn't need the second pass. But when the original question has k=2 and 1 guaranteed majority there's no way to know whether we "should" generalize it as guaranteeing 1 such element or guaranteeing k-1. The stronger the guarantee, the easier the problem.

Answer 2

Using Boyer-Moore Majority Vote Algorithm, we get:

vector<int> majorityElement(vector<int>& nums) {
    int cnt1=0, cnt2=0;
    int a,b;
    for(int n: A){
      if (n == a) cnt1++;
      else if (n == b) cnt2++;
      else if (cnt1 == 0){
        cnt1++;
        a = n;
      }
      else if (cnt2 == 0){
        cnt2++;
        b = n;
      }
      else{
        cnt1--;
        cnt2--;
      }
    }
    cnt1=cnt2=0;
    for(int n: nums){
        if (n==a) cnt1++;
        else if (n==b) cnt2++;
    }
    vector<int> result;
    if (cnt1 > nums.size()/3) result.push_back(a);
    if (cnt2 > nums.size()/3) result.push_back(b);
    return result;
}

Updated, correction from @Vipul Jain

Answer 3

You can use Selection algorithm to find the number in the n/3 place and 2n/3.

n1=Selection(array[],n/3);
n2=Selection(array[],n2/3);
coun1=0;
coun2=0;

for(i=0;i<n;i++)
{
    if(array[i]==n1)
      count1++;
    if(array[i]==n2)
      count2++;
}
if(count1>n)
   print(n1);
else if(count2>n)
   print(n2);
else
   print("no found!");

Answer 4

I use the following Python solution to discuss the correctness of the algorithm:

class Solution:
    """
    @param: nums: a list of integers
    @return: The majority number that occurs more than 1/3
    """
    def majorityNumber(self, nums):
        if nums is None:
            return None
        if len(nums) == 0:
            return None

        num1 = None
        num2 = None
        count1 = 0
        count2 = 0

        # Loop 1
        for i, val in enumerate(nums):
            if count1 == 0:
                num1 = val
                count1 = 1
            elif val == num1:
                count1 += 1
            elif count2 == 0:
                num2 = val
                count2 = 1
            elif val == num2:
                count2 += 1
            else:
                count1 -= 1
                count2 -= 1


        count1 = 0
        count2 = 0

        for val in nums:
            if val == num1:
                count1 += 1
            elif val == num2:
                count2 += 1

        if count1 > count2:
            return num1

        return num2

First, we need to prove claim A:

Claim A: Consider a list C which contains a majority number m which occurs more floor(n/3) times. After 3 different numbers are removed from C, we have C'. m is the majority number of C'.

Proof: Use R to denote m's occurrence count in C. We have R > floor(n/3). R > floor(n/3) => R - 1 > floor(n/3) - 1 => R - 1 > floor((n-3)/3). Use R' to denote m's occurrence count in C'. And use n' to denote the length of C'. Since 3 different numbers are removed, we have R' >= R - 1. And n'=n-3 is obvious. We can have R' > floor(n'/3) from R - 1 > floor((n-3)/3). So m is the majority number of C'.

Now let's prove the correctness of the loop 1. Define L as count1 * [num1] + count2 * [num2] + nums[i:]. Use m to denote the majority number.

Invariant

The majority number m is in L.

Initialization

At the start of the first itearation, L is nums[0:]. So the invariant is trivially true.

Maintenance

1. if count1 == 0 branch: Before the iteration, L is count2 * [num2] + nums[i:]. After the iteration, L is 1 * [nums[i]] + count2 * [num2] + nums[i+1:]. In other words, L is not changed. So the invariant is maintained.

2. if val == num1 branch: Before the iteration, L is count1 * [nums[i]] + count2 * [num2] + nums[i:]. After the iteration, L is (count1+1) * [num[i]] + count2 * [num2] + nums[i+1:]. In other words, L is not changed. So the invariant is maintained.

3. f count2 == 0 branch: Similar to condition 1.
4. elif val == num2 branch: Similar to condition 2.
5. else branch: nums[i], num1 and num2 are different to each other in this case. After the iteration, L is (count1-1) * [num1] + (count2-1) * [num2] + nums[i+1:]. In other words, three different numbers are moved from count1 * [num1] + count2 * [num2] + nums[i:]. From claim A, we know m is the majority number of L.So the invariant is maintained.

Termination

When the loop terminates, nums[n:] is empty. L is count1 * [num1] + count2 * [num2].

So when the loop terminates, the majority number is either num1 or num2.

Answer 5

At line number five, the if statement should have one more check:

if(n!=b && (cnt1 == 0 || n == a))

Answer 6

If there are n elements in the array , and suppose in the worst case only 1 element is repeated n/3 times , then the probability of choosing one number that is not the one which is repeated n/3 times will be (2n/3)/n that is 1/3 , so if we randomly choose N elements from the array of size ‘n’, then the probability that we end up choosing the n/3 times repeated number will be atleast 1-(2/3)^N . If we eqaute this to say 99.99 percent probability of getting success, we will get N=23 for any value of “n”.

Therefore just choose 23 numbers randomly from the list and count their occurrences , if we get count greater than n/3 , we will return that number and if we didn’t get any solution after checking for 23 numbers randomly , return -1;

The algorithm is essentially O(n) as the value 23 doesn’t depend on n(size of list) , so we have to just traverse array 23 times at worst case of algo.

Accepted Code on interviewbit(C++):

  int n=A.size();
  int ans,flag=0;
  for(int i=0;i<23;i++)
  {

int index=rand()%n;
int elem=A[index];
int count=0;
for(int i=0;i<n;i++)
{
    if(A[i]==elem)
    count++;
}

if(count>n/3)
{
    flag=1;
    ans=elem;
}

if(flag==1)
break;
}

if(flag==1)
 return ans;
else return -1;
 }