Problem Statement -
Electing Prime Cabinet
Members of BAAP party!!!
BAAP party president Mr. Panna decided to choose
the Prime Cabinet Members for his party from each state of the country Youngistaan.
The criterion decided by Mr.
Panna is that from each state having a population of N, N votes will be
casted. If a candidate gets more than
N/2 votes, he/ she will be elected as Prime Cabinet Member of BAAP party.
Given that population of each
state be N, where N should be maximum 10, 00000 for each state. Assume that
each individual will cast the vote.
Help Mr. Panna design an automated
system to get the Prime Cabinet Members from each state, if any. If a member contesting
for the cabinet member post from a state gets more than half (> N/2) of the
total population votes, he/ she will be appointed as Prime Cabinet Member of
BAAP party else the post will be vacant.
Write an algorithm to help Mr.
Panna appoint the cabinet member for the BAAP party.
Each of the contesting members
will be allotted a positive integer number.
Given the population of each
state N, write a method int primeMember
(int P []); which should return the prime member of array P, where P will
be the population array of a given state of size N. The method must return −1, if array P does not
have a prime member.
Input Specification:
A population array P, of size N (a state population) in random order where each array index denotes a member’s vote of the given state for his/her candidate denoted by a positive integer (candidate number).
A population array P, of size N (a state population) in random order where each array index denotes a member’s vote of the given state for his/her candidate denoted by a positive integer (candidate number).
Output Specification:
Single integer value
if the prime member exists, else -1(minus one).
Complexity:
Expected worst-case time complexity is O (N).
Expected worst-case space complexity is O (1).
Example 1:
For example, given population array P having candidate 2, 3,
4, 6 contesting from a state having the total population of N=12, such that
each person from the state casted his/ her vote for one of the above candidate
as below:
{4, 3, 3, 4, 2, 4, 3, 3, 6, 3, 3, 4}
The method should return −1, because the candidate 3 got the
maximum vote 6 out of all the candidates contesting and 6 votes is not more
than half of total population 12.
Example 2:
For example, given population array P having candidate 2, 3,
7, 10 contesting from a state having the total population of N=7, such that
each person from the state casted his/ her vote for one of the above candidate
as below:
{7, 3, 3, 10, 3, 3, 2}
The method should return 3, because the candidate 3 got the
maximum vote 4 out of all the candidates contesting and 4 votes is more than
half of total population 7.
