Who Won the Election???

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
17 upvotes
Asked in companies
AtlassianIBM

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
B--A-
Sample Output 1:
B
Explanation of Sample input 1:
Initially, B is at the 0th position, and A is at the 3rd position. in one move, B will be at 1st position, while A will be at 2nd position. So B gained and A both gained one supporter. Finally, B gains an extra supporter at the 4th position, as A will never be able to travel at that position. so overall B supporters are 3, and A supporters are 2. Hence B's supporters will win.
Sample Input 2:
1
B---A
Sample Output 2:
Coalition
Hint

Brute Force Approach.

Approaches (2)
Brute Force Approach.

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.
Time Complexity

O(N^2), Where ‘N’ is the length of the string.


As we have used two nested loops, complexity is O(N^2)

Space Complexity

O(1)


As we are using constant extra memory.

Code Solution
(100% EXP penalty)
Who Won the Election???
Full screen
Console