Last Updated: 25 Dec, 2020
Who Won the Election???
Moderate
Asked in companies
Elections are going on, and there are two candidates A and B, contesting with each other. There is a queue of voters and in this queue, some of them are supporters of A and some of them are supporters of B. Many of them are neutral. The fate of the election will be decided on which side the neutral voters vote. Supporters of A and supporters of B make attempts to win the votes of neutral voters.
The way this can be done is explained below:
1. The voter queue is denoted by three characters, viz {-, A, B}. The ‘-’ denotes neutral candidate, ‘A’ denotes supporter of candidate A and ‘B’ denotes supporter of candidate B.
2. Supporters of A can only move towards the left side of the queue.
3. Supporters of B can only move towards the right side of the queue.
4. Since time is critical, supporters of both A and B will move simultaneously.
5. They both will try and influence the neutral voters by moving in their direction in the queue. If a supporter of A reaches the neutral voter before a supporter of B reaches him, then that neutral voter will become a supporter of candidate A.
6. Similarly, if a supporter of B reaches the neutral voter before supporter of A reaches him, then that neutral voter will become a supporter of candidate B.
7. Finally, if both reach at the same time, the voter will remain neutral. A neutral vote cannot decide the outcome of the election.
8. If finally, the queue has more votes for candidate A, then A wins the election. If B has more votes, then B wins that election. If both have equal votes, then it will be a coalition government.
Your task is to find the outcome of the election.
For Example:
Given string- “B--A-”
B ---> B A <--- A B
----------------------------->
Output - B as B can move towards right only and A can move in left direction only. Thus B has 3 supporters in total while A have only 2 supporters.
Note:
1. There are no test cases where all votes are neutral.
2. The influenced voters do not move and hence does not have any influence over the neutral voters.
Input Format:
The first line of the input contains a single integer T, representing the number of test cases.
The first line of each test case will contain the string having characters ‘A’, ‘B’ or ‘-’
Output Format:
For each test case, you need to print ‘A’ if A wins the election, ‘B’ if B wins the election or ‘Coalition’ if both have equal votes.
Output for each test case will be printed in a separate line.
Note:
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10^4,
Where T is the number of testcases,
and N is the length of the string.
Time Limit: 1sec
Approaches
In this approach, we use the brute force approach to solve the problem. We traverse over each character of the given string and if the ith character is ‘-’ we use another loop to check on its right and left for either supporter of A or B.
Steps :
- Maintain the count of votes of A and B in variables.
- If the character of string at index i is ‘A’ or ‘B’, simply increment the count of votes of A or B respectively.
- If the character at index i is ‘-’, then we have to check which supporter is at a minimum distance from this neutral supporter.
- Use a variable minDist to maintain the minimum distance from the neutral supporter.
- Iterate on the left part of string, i.e. towards 0 to find if there is any supporter of B is present and store it’s distance in the minDist variable.
- Similarly iterate on the right part of string, i.e. towards the last element of string to find and store the distance of supporter of A.
- If distance of supporter of B is less than that of A, increment vote count of B, otherwise if distance of supporter of A is less than that of B, increment vote count of A.
- After traversing the complete string, return “A”, “B” or “Coalition”, if A has more votes or B has more votes or in case of a tie respectively.
In this approach, we use extra space to store the distance of supporters of A and B for each index.
Steps:
- Maintain the count of votes of A and B in variables.
- Maintain two extra arrays distanceA and distanceB to store distance of supporters of A and B respectively.
- Now traverse the string at each characters to count the number of voters for each group.
- If the character of string at index i is ‘A’ or ‘B’, simply increment the count of votes of A or B respectively.
- If the character at index i is ‘-’, then we have to check which supporter(either A or B) is at a minimum distance from this neutral supporter.
- We can check this by simply comparing the distance from the distance arrays.
- If distance of supporter of B is less than that of A, increment vote count of B, otherwise if distance of supporter of A is less than that of B, increment vote count of A.
- After traversing the complete string, return “A”, “B” or “Coalition”, if A has more votes or B has more votes or in case of a tie respectively.