Question

Design an O(n) algorithm that determines whether or not there is a majority in a list of elements. For example, [3,2,1] is NO and [3,1,3] is YES.

I want an answer that doesn't require the use of dictionaries/hash maps. It cannot be "Moore's voting algorithm" or a variation of it. The algorithm also can not use linear sorting algorithms because the input can not be assumed to satisfy the required conditions for any of the linear sorting algorithms my professor discussed in class.

Answer 1

public class Mejority {

   //driver program to test
   public static void main(String[] args) {
       int ar[]={1,2,3};
       mejority(ar);
       ar=new int[]{3,1,3};
       mejority(ar);

   }
   static void mejority(int ar[]){
      
       int size=max(ar); //size of new temp array as maximum element +1
       int temp[]=new int[size+1]; //new temp array
       for(int i=0;i<ar.length;i++){ //for each element of ar[i]
           temp[ar[i]]++; //suppose ar[i]=1 then increase the temp[1] element by 1 ie 1th count is now 1
                               //when next time ar[i] comes as 1 then this time temp[1] will be 2 ie count of 1 is 2 now
       }
       int mej=ar.length/2; //half of the length of original array
       for(int i=0;i<temp.length;i++){
          
           if(temp[i]>mej){ //if that element count greater then half of the length then print yes
               System.out.println("YES");
               return;
           }
       }
       System.out.println("NO");
   }
   //finds the max element is array
   static int max(int ar[]){
       int res=-1;
       for(int i=0;i<ar.length;i++){
           if(res<ar[i])
               res=ar[i];
       }
       return res;
   }
}

output

NO
YES