CareerCup

It shows three dots instead of question?

Yep ! this is a majority vote problem ... and the fastest known algorithum for this problem has been suggested by Prof Robert Boyer.

It goes like this [ writing for a C program ]

void findMajorityElement( int Arr[] , int N){

int count=0; int guess=0;

for (int i=0; i<N ; i++ ){

if(count==0){

guess = Arr[i];

count++;

}//end of the count =0 if statement

else{

if(guess==Arr[i]){

count++;

}else{   count--;  }

}

}//end of the for loop

printf("The  element with the majority element is %d", guess);

}//end of the findME function

Naive approach:
-Sort the array. Now run a scan and find the number with occurences > n/2
Complexity: O(nlogn)

Make pairs of elements, throw pairs with different elements, keep pairs with the same elements.
Then the pairs kept must less than n/2, and more than half pairs with the elements we are looking for.
Treat each pair as an new element, repeat the process until there is only one group.

take two buckets
first element in bucket1
second element if different from first one then in bucket 2
else in bucket 1
if 3 rd element is different from both buckets then pop both buckets and forget 3 rd element
continue this till array ends.
finally the elements in the buckets may be the elements so we have to lookup two scans for the elements in buckets finally.
So time=3n ie O(n)

import java.util.HashMap;

public class sortnbytwo {

public static void main(String args[]) {
int a[] = { 1, 2, 2, 4, 2, 2, 4, 233, 2, 4 };
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int cnt = 0;
for (int i = 0; i < a.length; i++) {
if (hm.containsKey(a[i])) {
cnt = hm.get(a[i]);
cnt++;
if(cnt==a.length/2){
System.out.println(a[i]);
break;
}
hm.put(a[i], cnt);
} else
hm.put(a[i], 1);
}
}
}

import java.util.HashMap;

public class sortnbytwo {

public static void main(String args[]) {
int a[] = { 1, 2, 2, 4, 2, 2, 4, 233, 2, 4 };
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int cnt = 0;
for (int i = 0; i < a.length; i++) {
if (hm.containsKey(a[i])) {
cnt = hm.get(a[i]);
cnt++;
if(cnt==a.length/2){
System.out.println(a[i]);
break;
}
hm.put(a[i], cnt);
} else
hm.put(a[i], 1);
}
}
}

Let the first element be required element(say result).Take a variable count initially initialized to 1.now start scanning the array from 2nd element.if element is same as result then increase the count else decrease the count.When count reaches to 0,make result as current element and initialize count to 1.At the end,result will contain the required element.

Here is the "single pass" O(N) solution:

function find_the_most_repeating(array)
   declare traverser_pair[key:int, count:int]
   traverser_pair.key = array[0]
   traverser_pair.value = 1 //init
   iterate "i" over array from 1 to array.length - 1
       if (traverser_pair.key == array[i])
           traverser_pair.value++
       else
		   if (--traverser_pair.value == 1)
			   //here comes the new dominant value
			   traverser_pair.key = array[i]
			   traverser_pair.value = 1
			
			   
	return traverser_pair.key;

HashMap<Integer, Integer> occurence = new HashMap<Integer, Integer>();

for(int i:array){
if(occurence.contains(i))occurence.put(i,occurence.get(i)+1);
else occurence.put(i,1);
}

time: O(n)

for(int i:occurence.keyset()){
if(occurence.get(i)>N/2)return i;
}

return -1;

import java.util.HashMap;
int find(int[] array){
HashMap<Integer, Integer> occurence = new HashMap<Integer, Integer>();

for(int i:array){
if(occurence.containsKey(i))occurence.put(i,occurence.get(i)+1);
else occurence.put(i,1);
}
for(int i:occurence.keySet()){
if(occurence.get(i)>array.length/2)return i;
}

return -1;
}

this is a majority vote problem.

An O(n )algo with space complexity O(1). This algo gives correct result iff majority element occurs >n/2, otherwise result is unpredictable.

public class mostoccurence {
public static void main(String args[]){
int a[]={1, 1, 1,1,1, 2, 2, 3, 3};//{2,5,3,5,3,6,3,5,5,3,5,5,5,5,0,9,3};
int n=a.length;
int count=0,x=0;

for(int i=0;i<n;i++)
{
if(count==0)
{
x=a[i];
count++;
}
else if(a[i]==x)
{count++;}
else count--;

}
if(count<=0)System.out.print(n+"Nothing");
else System.out.print(n+" "+x);
}
}

An O(n )algo with space complexity O(1). This algo gives correct result iff majority element occurs >n/2, otherwise result is unpredictable.

public class mostoccurence {
	public static void main(String args[]){
	int a[]={1, 1, 1,1,1, 2, 2, 3, 3};//{2,5,3,5,3,6,3,5,5,3,5,5,5,5,0,9,3};
	int n=a.length;
	int count=0,x=0;
	
	for(int i=0;i<n;i++)
	{
		if(count==0)
		{
			x=a[i];
			count++;
		}
		else if(a[i]==x)
		{count++;}
		else count--;
		
	}
if(count<=0)System.out.print(n+"Nothing");
else System.out.print(n+" "+x);
}
}

a=[int(x) for x in raw_input().split(' ')]
c=0;
e=None
for i in a:
	if c==0:
		e=i;
		c=1
	elif e==i:
		c+=1;
	elif e!=i:
		c-=1;
c=0;
for i in a:
	if i==e:
		c+=1
if c>=(len(a)+1)/2:		
	print e	
else:
	print None