CareerCup

This can be done in O(n) time and O(1) space. Since we have "more than a half" of the candidates we take the politicions in pairs. To explain it clearly I would use array A[] of n elements which only use equal() and an KeyValueEntry - here the key is the polition and value is int (count) of the politiotions. So what we do:

1.) for each A we check if the key in KeyValueEntry
1.1.) if they match count++ the value (KeyValueEntry ).
1.2.) if the KeyValueEntry is empty or the count == 0 we change the element with the new one and count = 1
1.3) if the KeyValueEntry has count > 0 we change the element with "count - 1"
2.) as soon as there are no more elements in A[] we know that the element left in the KeyValueEntry is the majority one since they have "more than a half".

I think that is it. If I miss something please write a comment :)

The simple O(n^2) is evident where each delegate is made to greet every other and hence checked if it belong to the majority party.

There is an elegant O(n) algorithm: Go through all delegates. Keep a counter and current guess for delegate of majority party, for each delegate the guessed delegate meet with smile, increase the counter and for each stare decrease the counter. When counter is zero, update the guess with the next delegate that you pick (at initialization, the first delegate is the guess).
When you have gone through all delegates, confirm that the delegate that you have chosen is indeed the one from majority party (this check not required if question ensures that there is a majority party)

For correctness of O(n) algorithm, search for 'Finding majority element in an array'

This is similar to majority vote algorithm, compare the successive members by making them greet. if they stare at each other the count remains 0 , else make the count 2 to begin with.
Also when you increment the count , mark the political party(call it X)

Now when 2 persons (adjacent to each other ) meet and they stare, then you make him meet one of the member's from party X. if they smile then he is also from party X, so increment the counter, else decrement the counter.
The rest is straight forward

* Majority party has more than half delegates.

1.for each delegate make set, mark set with smell flag.
2. keep union smell set to half of previous smell set number.
--compare root in each set , if friendly, then mark smell, else, remove both from smell sets.
3. keep union until only one smell set, then any element in set is major party delegate.

Why this may correct:
1. will generate n smell sets.
first time run 2. will reduce smell set to at most n/2, but no less than 1 smell set. get from *.
3. each run of 2 can at least shrink smell set by half.* still hold in each iteration result.
4. output smell set must be majority party delegates set with no less than one element.

Time complexity:
O(n lgn )

create an array of size n e.g. Arr[n] (all elements initialised to 0)
pick a person randomly say x1 (out of x1, x2....xn)
compare this person with other n-1 persons.
for x1's interaction with x2 -> make Arr[1]=1 for smile else let it remain 0
similarly for x1's interaction with kth x, make Arr[k-1]=1 for smile else let it remain 0
after this one round of interaction. just find the sum of values in Arr[0] to Arr[n-1]
If x1 was of non-majority party then he gave more stares than smiles and hence the sum is less than n/2. in such a case drop all the x's corresponding to the entry of 1 in the Arr (since they were of the same party as that of x1;
now repeat the whole process for remaining people.
we need to repeat this till the sum of All 1's in the Arr after a particular round of interactions is greater than ORIGINAL n/2.
This is because as soon as a randomly chosen (e.g.suppose x1) member makes smiling interaction for at least n/2 times then that member (and all those with whom he smiled during interaction ... i.e. all those corresponding to entry 1 in Arr) belong to the majority party

Thus for any given X1 ... we can find if he belongs to majority or not in n-1 interactions itself.
and if wish to dissect the majority from others, we actually keep dissecting parties till we fortunately dissect a party which occupies more than half space/count

How about the following approach.

Think it as a circular array. A[n].
Politicians are from 1 to n.
Introduce 1->2, 2-> 3,....... ,n->1.
A[i] = 1 if smile else 0.

iterate array and find the maximum number of contiguous 1s.

That contiguous sequence will be from majority party.

O(n) complexity.

How it will work. let say n is even. if people are kept at random position irrespective of their party. and we know that more than n/2 people are from majority class then definitely there will a set in array having most number of 1s.

in case of n being odd, circular array will take care of that.

Please let me know if I am wrong.

Here's an algorithm with O(n) time and O(1) space. Have one variable keep track of current member and another variable keep track of the counter:

1. Initially current member is the first member and counter is 1.
2. introduce the next member to current member. If they belong to the same party then increment the counter of current member; otherwise decrement the counter. If the counter becomes 0 then replace the current member with the next member and set its counter to 1.
3. repeat step 2 until either counter exceeded majority half or all members have been introduced. The current member remaining is the majority member.

The idea is to get rid off each minority member by pairing it up with either a majority member or another minority member. For example, say there are 9 total members of 5 majority and 4 minority, in the worst case, the order of introduction results in 4 minority cancel out with 4 majority, there is still one majority left to give the correct result.

public class Convention
{
	private PoliticalParty majorityParty;

	enum PoliticalParty
	{
		A, B;
	}

	static class Delegate
	{
		private PoliticalParty party;

		private Delegate(PoliticalParty party)
		{
			this.party = party;
		}

		private boolean hasSamePartyGreeting(Delegate other)
		{
			return (party == other.party);
		}

		public String toString()
		{
			return party.name();
		}
	}

	private Delegate[] delegates;

	public void init(int conventionSize)
	{
		int m = PoliticalParty.values().length;
		Random random = new Random();
		int idx = random.nextInt(m);
		majorityParty = PoliticalParty.values()[idx];

		int mpCount = 0;

		delegates = new Delegate[conventionSize];

		for (int i = 0; i < conventionSize; i++)
		{
			boolean finished = false;
			PoliticalParty randomParty = null;
			while (!finished)
			{
				random = new Random();
				idx = random.nextInt(m);
				randomParty = PoliticalParty.values()[idx];
				if (majorityParty == randomParty)
				{
					mpCount++;
					finished = true;
				} else
				{
					if ( i - mpCount + 1 < (conventionSize / 2 + conventionSize % 2) )
					{
						finished = true;
					}
				}
			}
			delegates[i] = new Delegate(randomParty);
		}
	}

	public boolean findMajority(int j)
	{
		int majority = 0;
		int n = delegates.length;

		for (int i = 0; i < n; i++)
		{
			if ( i != j )
			{
				if (delegates[j].hasSamePartyGreeting(delegates[i])) majority++;
				if (majority >= n / 2) return true;
			}
		}
		return false;
	}

	public static void main(String[] args)
	{
		int j = 0;
		Convention c = new Convention();
		c.init(3);
		System.out.println( String.format( "Is %s a member of the majority party %s: %s",
				c.delegates[j],
				c.majorityParty, c.findMajority(j)));
		for (Delegate d : c.delegates)
		{
			System.out.print(d + ", ");
		}
	}

}

The algorithm seems pretty straightforward. O(n). So the exit clause of checking if we met more than 1/2 the majority of delegates who belong to the party, then we can quit checking. The solution above works for any arbitrary number of political parties as well.

Did I overlook something?

1 randomly select one person, introduce him to all other people.
If more than half smiles to him, already find all members of the majority party,
Otherwise the selected people does not belong to the majority party,
and all people smiles to him belong to one minority party. Then

2 Randomly choose one people does not belong to any known minority party,
introduce him to all other people does not belong to any known minority party.

3. Repeat 2 until find one people belongs to the majority party.

Assume there are m parties, the algorithm complxity is O(n x m)

public Politician FindMajorPoliticalParty(Politician[] input)
        {
            if (input == null || input.Length == 0)
            {
                throw new ArgumentException();
            }

            List<PoliticianAlien> symbol = new List<PoliticianAlien>();

            int max = 1;
            bool findGroup = false;
            symbol.Add( new PoliticianAlien(input[0], 0));
            for (int i = 1; i < input.Length; i++)
            {
                findGroup = false;
                for (int j = 0; j < symbol.Count; j++)
                {
                    if (symbol[j].Symbol.IsTheSameParty(input[i]))
                    {
                        symbol[j].AlienCount++;
                        if (symbol[j].AlienCount > max)
                        {
                            symbol.Sort((m, n) => { return m.AlienCount > n.AlienCount ? 1 : 0; });
                            max = symbol[j].AlienCount;

                            if (max > input.Length /2)
                            {
                                return symbol[j].Symbol;
                            }
                        }
                        findGroup = true;
                        break;
                    }

                    if (findGroup)
                    {
                        continue;
                    }
                    else
                    {
                        symbol.Add(new PoliticianAlien(input[i], 0));
                    }
                }
            }

            return symbol[0].Symbol; ;
        }

        internal class PoliticianAlien
        {
            public Politician Symbol { get; set; }
            public int AlienCount { get; set; }

            public PoliticianAlien(Politician user, int count)
            {
                this.Symbol = user;
                this.AlienCount = count;
            }
        }

        public class Politician
        {
            public string Name{get;set;}
            private PoliticalParty Party {get; set;}

            public bool IsTheSameParty(Politician user)
            {
                return this.Party.PartyName.Equals(user.Party.PartyName, StringComparison.InvariantCultureIgnoreCase);
            }
        }

        public class PoliticalParty
        {
            public string PartyName {get; set;}
        }

Select person A to represent party A (of unknown affiliation at this point), create another set of ~A to represent his opposite.

Then for each delegate x
introduce x to A via greeting function
if A is same party add x to A
else add x to ~A

At the end person A will be very tired but you will have two sets of delegates. This algorithm would easily parallelize, we could have separate people "threads" creating two separate sets. At the end we can merge by comparison just two people from each set and merge appropriately.

This requires O(N) greetings and testing membership is O(1) since we are using a set.

O(2n).
Put all the delegates in an array.
First time, iterate and try to join delegate with the delegate on the right if they belong to the same party.
Second time, iterate and try to join delegate with the delegate on the right of the delegate on the right. That is, jump one delegate.
Since join search set can be done in constant time, and more than n/2 delegates belong to same party, after two loops, one set will be of size >= n/2.

// check the below code taken from stackoverflow
int findMajorityElement(int * arr, int size) { 
     int count = 0, i, majorityElement;
     for (i = 0 ;  < size ; i++) {
        if(count == 0) {
            majorityElement = arr[i];
        }
        if(arr[i] == majorityElement) 
           count++;
        else 
           count--;
     }
     count = 0;
     for (i=0; i < size ; i++) {
          if (arr[i] == majorityElement) {
                count++;
          }
     }
     if ( count > size/2) {
          return majorityElement;
     }
     else return -1;
}

Hi ,
Can anybody give recursive algorithm for this question?

#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;

/*========================================Templates=============================================*/
#define Testcases(tc)	int tc;	S(tc);	while(tc--)
#define REP(i,n)		for(int i=0;i<(n);++i)
#define FOR(i,a,b)		for(int i=(a);i<=(b);++i)
#define FORN(i,a,b,n)	for(int i=(a);i<=(b);i+=n)
#define FORD(i,a,b)		for(int i=(a);i>=(b);--i)
#define FORDN(i,a,b,n)	for(int i=(a);i>=(b);i-=n)
#define FOREACH(i,c)	for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define ALL(x)			(x).begin(),(x).end()
//#define S(n)			scanf("%d",&n)
#define S2(n1,n2)		scanf("%d %d",&n1,&n2)
#define S3(n1,n2,n3)	scanf("%d %d %d",&n1,&n2,&n3)
#define SL(n)			scanf("%lld",&n)
#define SD(n)			scanf("%f",&n)
#define SS(a)			scanf("%s",a)
#define DB(x)			cout<<#x<<" : "<<x<<endl;

typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned int UINT;

/*======================================IO OPTIMISED FUNCTIONS===================================*/
int sign;
int ch;
inline void S( int &x )
{
	x=0;
	while((ch<'0' || ch>'9') && ch!='-' && ch!=EOF)	ch=getchar();
	if (ch=='-')
		sign=-1 , ch=getchar();
	else
		sign=1;

	do
	x=(x<<3)+(x<<1)+ch-'0';
	while((ch=getchar())>='0' && ch<='9');
	x*=sign;
}
/*===============================================================================================*/


int main()
{
	int N,T, temp, x, k;
	
	S(T);
	while(T--)
	{
		int arr[1000];
		int tempArr[503];
		bool flag;
		S(N);
		FOR(i,1,N)
			S(arr[i]);          
		while(1)
		{
			flag = false;
			temp = 0;
			x = 1;      
			k = 1;          
			if(N%2)
			{
				x = 2;
				temp = arr[N];
			}

			FORN(i,1,N-x,2)
			{
				if(arr[i] == arr[i+1])
				{
					tempArr[k++] = arr[i];
					flag = true;
				}
			}
			if(temp)
			{
				tempArr[k] = temp;
			}
			else
			{
				if(flag)
					k--;
			}
			FOR(i,1,k)
				arr[i] = tempArr[i];
			N = k;
			if(k==1)
				break;    
		}       
		printf("%d\n",arr[1]);           
	}
	return 0;
}

Basically, the idea is to reduce the list to n/2 by each while(1) iteration. The order would remain n/2+n/2*2+...

Tested with following inputs -

15
10
1 2 1 3 1 4 1 5 1 1
10
1 1 2 2 3 3 1 1 1 1
10
1 2 1 1 1 2 1 2 1 2
5
1 2 1 1 3
2
1 1
3
1 2 1
5
1 2 1 3 1
5
1 1 1 2 3
5
1 2 3 1 1
5
2 3 1 1 1
5
1 2 3 1 1
5
1 2 1 1 2
5
3 2 1 1 1
5
2 3 1 1 1
5
1 1 2 3 1

And o/p is 1 for each case. Please suggest if there is something which I missed.

Assuming n is even, ask the delegates to greet in pairs (n/2 greets). Delegates in pair that laughs are from same party.

Assuming n is odd, ask delegates to greet in pairs ( (n-1)/2 greets). One delegate stands aside. Two cases are possible
1. None of the delegates greeting each other laughs ==> Delegate standing aside is from majority party
2. Delegates greeting each other laughs ==> Delegates in laughing pair are from majority party

O(n) time is fairly straight forward. Since each person belongs exclusively to 1 party we can simply introduce the same person to all other people and keep counters for both parties as well as the first or last person of the opposite party:
int oppositeIndex = 0;
int oppositeParty = 0;
int sameParty = 0;
for (int i = 1; i < n; i++){
if (A[0] matches A[i])
sameParty++;
} else {
oppositeParty++;
oppositeIndex = i;
}

Any ideas on how to get better than O(n)?